[자료구조] Linked List 직접 구현하기.

Linked list

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. (위키백과)

 

직접그린 링크드리스트 이미지

[구현하기]

class MyNode<T> {
  public next: null | undefined | MyNode<T>;
  public value: T;
  constructor(value: T) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList<T> {
  private head: MyNode<T>;
  private tail: MyNode<T>;
  private length = 0;

  constructor(value: T) {
    this.head = new MyNode(value);
    this.tail = this.head;
    this.length = 1;
  }

  get size(): number {
    return this.length;
  }

  append(value: T) {
    const NewNode = new MyNode(value);
    this.tail.next = NewNode;
    this.tail = NewNode;
    this.length++;
    return this;
  }

  insert(index: number, value: T) {
    const NewNode = new MyNode(value);
    if (index === 0) {
      NewNode.next = this.head;
      this.head = NewNode;
    } else if (index >= this.length) {
      this.append(value);
      return;
    } else {
      const prevNode = this.getNodeByIdx(index - 1);
      const currentNode = prevNode?.next;
      prevNode.next = NewNode;
      NewNode.next = currentNode;
    }

    this.length++;
  }

  remove(index: number) {
    if (index === 0) {
      this.head = this.head.next as MyNode<T>;
    } else {
      index = index >= this.length - 1 ? this.length - 1 : index;
      const prevNode = this.getNodeByIdx(index - 1);
      const currentNode = prevNode.next;
      prevNode.next = currentNode?.next;

      if (index >= this.length - 1) {
        this.tail = prevNode as MyNode<T>;
      }
    }

    this.length--;
    return this;
  }

  print() {
    let count = 0;
    let currentNode = this.head;
    let str = '';
    while (count < this.size) {
      if (count === this.size - 1) {
        return (str += `${currentNode.value}`);
      }
      str += `${currentNode.value} -> `;
      currentNode = currentNode.next as MyNode<T>;
      count++;
    }
  }

  private getNodeByIdx(index: number): MyNode<T> {
    let currentNode: MyNode<T> = this.head;
    let count = 0;

    while (count < index) {
      currentNode = currentNode.next as MyNode<T>;
      count++;
    }

    return currentNode;
  }
}

 

[사용하기]

const myLinkedList = new LinkedList('s');
myLinkedList.append('r');
myLinkedList.append('i');
myLinkedList.append('n');
myLinkedList.insert(1, 't');
myLinkedList.insert(5, 'g');

console.log(myLinkedList.print());

myLinkedList.remove(6).remove(5).remove(0);
console.log(myLinkedList.print());

결과

 

링크드 리스트는 배열과 그 차이가 있는데 삽입/삭제가 빠른 반면에 조회가 느리며, 크기가 동적이다