200910 [Linked List]

Linked List

 : node 들의 연결 구조로 head 와 tail을 가지고 있고 각 node는 다음 node의 값을 가지고 있는 구조이다.

 

1. Linked List의 장점과 단점

 : Linked List는 데이터와 link 주소 를 가지고 있는 node 들의 연결 이라고 볼 수 있다. 실제로 node 들이 연결 되어 있는것이 아니라 단순히 데이터가 다음 데이터의 주소를 가지고 있는 것이다. 이 node들 데이터와 주소 두가지를 모두 가지고 있어야 하는 특이한 데이터 이다.

Linked List의 구조

＠장점

 - node들의 link주소를 이용하면 데이터의 삽입과 삭제가 간편하다.

  : 만약 리스트의 모든 위치를 파악하고 있다면 단순하게 node.next를 바꿔주는것 만드로 어느 위치에서든 데이터를 삽입 할 수 있다.

 

＠단점

 -리스트의 위치를 모르는 상태에서는 원하는 위치를 찾기 위해서 O(n)의 시간 복잡도를 가지게 되기 때문에 좋다고만은 할 수 없다.

 

2. 배열과의 비교

 : Linked List는 배열의 기능과 유사한 기능을 가지고 있지만 배열과는 다르다. 배열은 Linked List와는 달리 연결된 구조를 가지고 있고 각각의 데이터에 index라는 위치가 부여되어 접근이 용이하여 원하는 데이터를 찾는데 O(1)의 시간복잡도를 가지지만 데이터의 삽입과 삭제 시 index를 변경해 줘야 하기 때문에 연산과정이 복잡해 진다는 단점이 있다.

 

※ 탐색과 정렬이 목적이라면 배열 / 데이터의 추가와 삭제가 목적이라면 연결리스트를 사용하면 된다.

 

3. Linked List 의 종류

1. Single Linked List

 : 단일방향을 가진 Linked List로 head 에서 시작하여 tail에서 연결이 끝난다.

 

2. Double Linked List

 : 시작점이 두곳인 Linked List로 모든 노드의 link 주소가 앞뒤로 하나씩 총 두 개의 주소를 가지고 있어는 구조이다. 

 

3. Circular Linked List

 : 마지막 tail 의 link 주소가 head 를 가리키고 있는 순환구조를 가지고 있다. 

※Circular 의 사전적 의미 - 회보 : 어디를 갔다가 다시 돌아옴.

 

4. Linked List의 code 구현

// 짬짬히 구현해 보겠다...ㅠ

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }
  
  addToTail() {}
  
  remove() {}
  
  getnodeAt() {}
  
  contains() {}
  
  indexOf() {}
  
  size() {}
  
}