Linked List

말그대로 서로 연결된 리스트다.
그림을 보며 이해해보자

그림 상 캡슐 모양으로 보이는 것 하나를 node(노드)라고 한다. 이 노드는 data의 value을 가지는 부분과 다음 리스트를 가리키는 pointer로 이루어져 있다.

가장 앞의 node는 Head 가장 마지막 node는 tail이라고 하고 tail의 pointer는 결국 null을 가르킨다.

시간 복잡도

Array와 비슷한 시간 복잡도인 O(n)을 가지지만 insert기능에서 더 복잡하지 않다.

Hash 보다는 insert가 복잡하지만 ordered list를 가질 수 있다는 장점이 있다.

Prepend , append => O(1)
lookup, insert, delete => O(n)

Linked list code

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
   }
   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;
 }
 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();
 }
}

Linked list 질문 -> reverse() 만들기

linked list에 관한 인터뷰 질문 중 가장 빈번한 질문은 linked list의 reverse() 기능을 만드는 것이다.
쉽지는 않다.

간략히 말로 우선 풀자면

• head 값을 first로 한다.
• tail이 head를 바라보게 한다.
• second값으로 first.next로 지정한다.
• second 값부터 second가 없을 때까지 reverse한다.
• head.next 를 null을 바라보게 한다.
• head값에 first를 넣는다.

코드를 보고 다시 보자

reverse() {
  // 값이 하나인 경우
     if (!this.head.next) {
       return this.head;
     }
     let first = this.head;
     this.tail = this.head;
     let second = first.next;
 // second부터 하나씩 돌리기
     while(second) {
       const temp = second.next;
       second.next = first;
       first = second;
       second = temp;
     }
 
     this.head.next = null;
     this.head = first;
     return
   }

참고
Udemy " Master the Coding Interview: Data Structures + Algorithms " - Zero To Mastery