자료구조(1) - Linked List

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/linked-list

참고: https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/linked-list/README.ko-KR.md

Linked List

자세한 구현 및 테스트는 직접 구현하고 여기서는 개념만 알아보자.

자기 자신의 값과 다음 노드를 가리키는 포인터로 이루어진 Linked List. 논리적 순서는 메모리의 물리적 저장 순서와 일치하지 않는다.

• 장점: 순회하는 동안 순서에 상관없이 효율적인 삽입이나 삭제가 가능하다.

• 단점: 접근 시간이 선형이고 병렬 처리 불가. 임의 접근처럼 빠른 접근 불가. 배열에 비해 낮은 캐시 지역성

Linked List는 결국 자료 구조이기 때문에 CRUD가 어떻게 이루어지는지 의사 코드로 알아보자.

우선 리스트와 노드의 간단한 구조이다.

# LinkedListNode.js

export default class LinkedListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
...
}

# LinkedList.js

import LinkedListNode from "./LinkedListNode";

export default class LinkedList {
  constructor(comparatorFunction) {
    this.head = null;
    this.tail = null;
  }
  ...
}

CRUD

삽입

# append(value)

리스트가 비었다면
  head와 tail을 새로운 노드로 추가:
  head = newNode
  tail = newNode

리스트의 끝에 새로운 노드를 추가:
tail.next = newNode
tail = newNode

# prepend(value)

새로운 노드 생성 시 next를 기존 head로 생성

head를 newNode로 설정:
head = newNode

tail이 없다면 즉 리스트가 비었다면
  tail을 newNode로 설정:
  tail = newNode

# insert(value, index)

index가 0 이하라면
  맨 앞에 값 추가:
  prepend(value);
index가 0 초과라면
  index까지 순회
  해당 index에 노드가 없다면
    append(value);
  해당 index에 노드가 있다면
    새로운 노드를 중간에 삽입:
    newNode.next = currentNode.next;
    currentNode.next = newNode;

탐색

# find(value)

빈 리스트라면
  null 반환:
  return null;
  
리스트 순회
  순회하는 노드의 value와 파라미터 value 값이 일치 한다면
    해당 노드 반환:
    return currentNode;
  
null 반환:
return null;

value가 객체일 수도 있는데 이는 callback 함수를 추가하여 좀 더 복잡한 find가 가능.
자세한 코드는 상단에 링크를 참고.

삭제

# delete(value)

빈 리스트라면
  null 반환:
  return null;
  
head가 존재하고 삭제되어야 한다면
  head 삭제:
  deletedNode = head;
  head = head.next;
  
리스트 순회(currentNode.next가 없을 때까지)
  순회하는 노드의 next value와 파라미터 value 값이 일치 한다면
  해당 노드의 next 삭제:
  deletedNode = currentNode.next;
  currentNode.next = currentNode.next.next;
  
tail이 삭제되어야 한다면
  tail 삭제:
  tail = currentNode;
  
삭제되는 노드 반환:
return deletedNode;

LinkedList의 특성 상 순회 중 이전 노드를 읽을 수 없으므로 currentNode의 next 값을 보고 순회해야 한다.
또한 currendNode.next를 기준으로 순회하므로 tail 삭제 시에는 그냥 tail을 current로 설정하면 된다.

삭제 또한 탐색과 마찬가지로 callback 함수를 추가하여 복잡한 연산이 가능할듯 하다.

기타

뒤집기

# reverse()

순회하면서 현재 노드의 next를 이전 노드로 설정
tail을 head로
head를 이전 노드로

여긴 좀 헤매서 전체 코드를 보자.

...
reverse() {
  let currNode = this.head;
  let prevNode = null;
  let nextNode = null;
  
  while (currNode) {
    nextNode = currNode.next; //1
    currNode.next = prevNode; //2
    prevNode = currNode; //3
    currNode = nextNode; //4
  }
  
  this.tail = this.head; //5
  this.head = prevNode; //6
  
  return this;
}

간단하게 리스트가 1->2->3 이렇게 있다고 생각하고 보면

순회	LinkedList	currNode	prevNode	nextNode
초기	1->2->3	1	null	null
1.1	1->2->3	1	null	2
1.2	1->null 2->3	1	null	2
1.3	1->null 2->3	1	1	2
1.4	1->null 2->3	2	1	2
2.1	1->null 2->3	2	1	3
2.2	2->1->null 3	2	1	3
2.3	2->1->null 3	2	2	3
2.4	2->1->null 3	3	2	3
3.1	2->1->null 3	3	2	null
3.2	3->2->1->null	3	2	null
3.3	3->2->1->null	3	3	null
3.4	3->2->1->null	null	3	null

5: 기존 3이었던 tail을 1로 설정
6: head를 prevNode인 3으로 설정
완성! (head)3->2->1(tail)

이렇게 하나하나 쓰고 보니 이해가 됐다.
이해는 했는데 그럼 내가 직접 작성할 수 있는가?
ㅋㅋ이제 작성했던 코드 다 지우고 내가 직접 작성해봐야겠다.

복잡도

시간 복잡도

접근	탐색	삽입	삭제
O(n)	O(n)	O(1), O(n)	O(n)

삽입에서 head나 tail에 삽입하는 것은 O(1)이지만 중간에 삽입하는 것은 O(n)

공간 복잡도

O(n)

---

상단 링크 보면 테스트 코드도 같이 있어서 다 지우고 내가 작성하고 테스트 돌려볼 수 있어서 더 좋은 것 같다. 나는 이 레포를 다 가져오진 않고 그냥 내가 필요한 부분만 작성했다.

https://github.com/cxzaqq/js-algorithms