TIL #32) Linked List 자료구조

 

Linked List

링크드 리스트란 노드라는 기본 요소를 사용해 선형적인 데이터 묶음을 추상적으로 표현한 것이다. 노드에는 데이터뿐만 아니라 다음 노드를 가리키는 참조(링크)가 포함되어 있다.

트렐로 프로젝트 중, 카드의 순서를 옮겨야하는 과제가 있었다.
무식하게 옮기려면 할수는있겠지만 만약 카드의 갯수가 100장, 1000장이 넘어간다면? 
한 순서를 옮기기위해 다른것도 모조리 수정이 필요할 것이다.
이럴때 사용할 수 있는게 링크드리스트 자료구조이다.

 

Singly Linked List

• Node: data와 pointer로 이루어진 요소로서 모여서 리스트를 형성
• data: 데이터
• pointer(link): 다음 Node를 가리키는 참조
• head: 가장 앞에 있는 Node
• tail: 가장 끝에 있는 Node

단방향일 경우에는 이렇고, 양방향일때는 이전 Node를 가리키는 참조(prev)도 들어간다.

 

아래 페이지에서 전체 코드를 확인하고 실습해 볼 수있다.

https://codesandbox.io/s/linked-list-exercise-2pju2

linked list exercise - CodeSandbox

 

Node

type Node<T> = {
  val: T;
  next: Node<T> | null;
};

• val: data를 담는다.
• next: 다음 노드를 가리키는 pointer다. 다음 노드가 없으면 null 값을 가진다.

Linked List 인터페이스

interface ILinkedList<T> {
  getAtIndex(index: number): T | null;
  addAtHead(val: T): void;
  addAtTail(val: T): void;
  addAtIndex(index: number, val: T): void;
  deleteAtIndex(index: number): void;
  size: number;
}

다음으로 구현하고자 하는 링크드 리스트의 인터페이스를 정의한다.

• getAtIndex(): 전달받은 인덱스 위치에 있는 노드의 데이터를 가져온다. 인덱스가 리스트의 범위를 벗어난 경우 null을 반환한다.
• addAtHead(): head에 노드를 추가한다.
• addAtTail(): tail에 노드를 추가한다.
• addAtIndex(): 전달받은 인덱스 위치에 노드를 추가한다. 인덱스가 리스트의 범위를 벗어난 경우 노드를 추가하지 않는다.
• deleteAtIndex(): 전달받은 인덱스 위치에서 노드를 삭제한다. 인덱스가 리스트의 범위를 벗어난 경우 노드를 삭제하지 않는다.
• size: 리스트의 길이를 반환한다.

Linked List 클래스

class LinkedList<T> implements ILinkedList<T> {
  constructor(private head: Node<T> | null = null, private _size: number = 0) {}

  /**
   * Time: O(1)
   */
  public get size() {
    return this._size;
  }
  // ...
}

• head: null로 초기화한다.
• _size: 0으로 초기화한다.
• size: _size의 getter 메서드이다.

/**
 * Time: Worst - O(n), Best - O(1)
 */
private getNodeAtIndex(index: number): Node<T> | null {
  if (index < 0 || index >= this.size) {
    return null;
  }

  let curr = this.head;  // head에서 출발한다.
  let count = 0;
  while (count < index) {  // index-1 노드에 도달할 때까지 반복
    curr = curr!.next;  // 현재 노드에서 다음 노드로 이동한다.
    count++;
  }
  // while문이 종료되면 index 노드가 curr에 담긴다.
  return curr; // 이 노드를 반환한다.
}

• getNodeAtIndex()

전달받은 인덱스 위치에 있는 노드를 찾아 반환하는 메서드이다. 인덱스가 리스트의 범위를 벗어날 경우 null을 반환한다. 이 메서드는 다른 메서드에서 노드를 찾기 위해 사용되므로 클래스 내에서만 접근할 수 있도록 private으로 설정한다.

/**
 * Time: Worst - O(n), Best - O(1)
 */
getAtIndex(index: number): T | null {
  const node = this.getNodeAtIndex(index);  // index 노드를 가져온다.
  if (node) {  // 노드가 있으면
    return node.val;  // 그 노드의 데이터를 반환한다.
  }
  return null;  // 노드가 없으면 null을 반환한다.
}

• getAtIndex()

전달받은 인덱스에 있는 노드의 데이터를 반환하는 메서드이다.

/**
 * Time: O(1)
 */
addAtHead(val: T): void {
  // 기존 head를 가리키는 새로운 노드를 만들고 이를 head로 바꾼다.
  this.head = { val, next: this.head };
  this._size++;  // 리스트의 사이즈를 하나 증가시킨다.
}

• addAtHead()

리스트의 맨 앞에 노드를 추가하는 메서드이다.

/**
 * Time: Worst - O(n), Best - O(1)
 */
addAtTail(val: T): void {
  if (this.size === 0) {  // 리스트가 비어 있으면
    this.addAtHead(val);  // 리스트의 맨 앞에 노드를 추가한다.
    return;
  }

  const lastNode = this.getNodeAtIndex(this.size - 1)!;  // tail을 가져온다.
  lastNode.next = { val, next: null };  // 기존 tail이 새로 만든 노드를 가리키도록 하여 이를 tail로 바꾼다.
  this._size++;  // 리스트의 사이즈를 하나 증가시킨다.
}

• addAtTail()

리스트의 맨 끝에 노드를 추가하는 메서드이다.

/**
 * Time: Worst - O(n), Best - O(1)
 */
addAtIndex(index: number, val: T): void {
  if (index < 0 || index > this.size) {
    return;
  }

  if (index === 0) {  // 리스트가 비어 있으면
    this.addAtHead(val);  // 리스트의 맨 앞에 노드를 추가한다.
    return;
  }

  const prevNode = this.getNodeAtIndex(index - 1)!;  // index-1 노드를 가져온다.
  // 새로운 노드를 만들고 index 노드를 가리키도록 한다.
  // index-1 노드는 이 새로운 노드를 가리키도록 한다.
  prevNode.next = { val, next: prevNode.next };
  this._size++;  // 리스트의 사이즈를 하나 증가시킨다.

• addAtIndex()

전달받은 인덱스 위치에 노드를 추가하는 메서드이다.

/**
 * Time: Worst - O(n), Best - O(1)
 */
deleteAtIndex(index: number): void {
  if (index < 0 || index >= this.size) {
    return;
  }

  if (index === 0) {  // 맨 앞에 있는 노드를 삭제하는 경우
    this.head = this.head!.next;  // head의 다음 노드를 head로 바꾼다.
  } else {  // 그렇지 않은 경우
    const prevNode = this.getNodeAtIndex(index - 1)!;  // index-1 노드를 가져온다.
    prevNode.next = prevNode.next!.next;  // index-1 노드가 index+1 노드를 가리키도록 한다.
  }
  this._size--;  // 리스트의 사이즈를 하나 감소시킨다.
}

• deleteAtIndex()

전달받은 인덱스 위치에서 노드를 삭제하는 메서드이다.

 

---

하지만 결론은,, 현재 쓰는 프레임워크에서 링크드리스트를 사용하는건 부적합하다는 것이다.
실제로 프로젝트에 적용해보니 링크드리스트 자료구조를 적용하는것은 가능하나, 이 노드에 대한 데이터를 어떻게 저장해야할지 방법을 찾지 못했다. 하려고 하면 가능은 하겠지만 결국 프레임워크의 기본 기능을 뛰어넘어야 내가 원하는대로 사용가능하다고 한다.. ^-^