ZTM Data Structures & Algorithms - Linked List

udemy 에서 Master the Coding interview: Data Structures & Algorithms 강의를 수강한 내용을 정리하는 포스팅입니다.

---

Linked List

https://en.wikipedia.org/wiki/Linked_list#:~:text=In%20computer%20science%2C%20a%20linked,which%20together%20represent%20a%20sequence.

Linked list - Wikipedia

- 연결리스트는 각 노드 별로 값과 다음노드를 가리키는 포인터를 저장해 연결시켜놓은 자료구조다. 

- 맨 처음 노드를 head 라고 하며 마지막 노드를 tail 이라고 부른다.
- 마지막 노드의 포인터는 null을 가리키게하여 마지막인것을 알수 있게 한다.  

자바스크립트로 구현한 단방향 linked list의 경우 아래와 같은 모습이 될수 있다. 
(아래의 코드를 양방향 으로 구현시 환형 참조가 일어나서 제대로 작동하지 않는 경우가 발생한다.... 이부분은 아직 어떻게 해결해야하는지 떠올리지 못했다.... 연결리스트를 양방향으로 구현하면 환형참조가 일어나는게 당연하다는 스택오버플로우 글을 보긴 했는데 정말 그런걸까? 나중에 해결책을 떠올리면 다시와서 양방향으로도 구현 해보도록 하자.)

class LinkedList {
    constructor(value) {
        this.head = {
            value: value,
            next: null
        };
        this.tail = this.head;
        this.length = 1;
    }
    
    append(value) {
      const newNode = {
        value: value,
        next: null
      }
      console.log(newNode)
      this.tail.next = newNode;
      this.tail = newNode;
      this.length++;
      return this;
    }
    
    prepend(value) {
      const newNode = {
        value: value,
        next: null
      }
      newNode.next = this.head;
      this.head = newNode;
      this.length++;
      return this;
    }
    
    printList() {
      const array = [];
      let currentNode = this.head;
      while(currentNode !== null){
          array.push(currentNode.value)
          currentNode = currentNode.next
      }
      return array;
    }
    
    insert(index, value){
      //Check for proper parameters;
      if(index >= this.length) {
        console.log('yes')
        return this.append(value);
      }
      
      const newNode = {
        value: value,
        next: null
      }
      const leader = this.traverseToIndex(index-1);
      const holdingPointer = leader.next;
      leader.next = newNode;
      newNode.next = holdingPointer;
      this.length++;
      return this.printList();
    }
    
    traverseToIndex(index) {
      //Check parameters
      let counter = 0;
      let currentNode = this.head;
      while(counter !== index){
        currentNode = currentNode.next;
        counter++;
      }
      return currentNode;
    }
    
    remove(index) {
      // Check Parameters      
      const leader = this.traverseToIndex(index-1);
      const unwantedNode = leader.next;
      leader.next = unwantedNode.next;
      this.length--;
      return this.printList();
    }
    
    reverse() {
      if (!this.head.next) {
        return this.head;
      }
      let first = this.head;
      this.tail = this.head;
      let second = first.next;
  
      while(second) {
        const temp = second.next;
        second.next = first;
        first = second;
        second = temp;
      }
  
      this.head.next = null;
      this.head = first;
      return this.printList();
    }
}

let myLinkedList = new LinkedList(10);
myLinkedList.append(5)
myLinkedList.append(16)
myLinkedList.prepend(1)
myLinkedList.printList()
myLinkedList.insert(2, 99)
myLinkedList.insert(20, 88)
myLinkedList.printList()
myLinkedList.remove(2)
myLinkedList.reverse()

-연결리스트의 장점과 단점은 아래와 같다. 

-포인터만 연결/삭제하면 되기 때문에 데이터의 삽입과 삭제가 빠르다(배열의 경우 중간의 데이터를 수정시 뒤에 오는 데이터를 메모리 내에서 다 옮겨야 해서 느렸다는 점을 기억하자).
-자료가 포인터를 통해 순차적으로 연결되어있어서 정렬 되어있다. 
-데이터의 인덱스를 저장해두지 않기 때문에 자료를 찾아보는데 최악의 경우 선형시간(O(n))이 걸릴수 있으며 다음 자료의 메모리 위치인 포인터를 저장하기 때문에 메모리 공간을 추가로 차지한다.