[CS] linked-list

linked-list란?

linked-list란 data elements의 순서가 있는 조합을 말한다. 각 데이터 요소들은 linked list에서는 node로 불린다.
각각의 node들은 두 파트를 포함한다. data와 다음 node에 대한 pointer가 그것이다.

array와의 차이점

array가 실제 메모리에서 연속적으로 위치하는데에 비해 linked-list는 그렇지 않다. pointer를 이용하여 다음 node의 위치를 알 수 있기 때문이다.

linked-list의 특징

• 연속적인 node들은 pointer에 의해 연결된다.
• head pointer는 list의 첫번째 node를 가리킨다.
• linked list의 사이즈는 프로그램 실행중에 커지거나 작아질 수 있다.
• 필요한만큼 얼마든지 만들 수 있다.
• array와는 달리 고정된 할당 메모리가 없으므로 elements가 늘어날 경우 limit이 존재하는 array에 비해 활용이 용이하다.
• array와 달리 메모리의 연속적 장소에 저장되지 않으므로 array와 달리 전체 데이터구조의 reorganization 없이 data의 신속한 삽입과 삭제가 가능하다.

단점

• node에 대한 접근은 반드시 첫번째 요소부터 시작되어야 하므로 중간 데이터로의 바로 접근이 힘들고 첫번째 요소부터 훑어오는 만큼 시간이 더 걸린다.
• pointer의 사용으로 인해 array보다 메모리를 더 먹는다.

linked-list의 종류

singly linkded list

일반적으로 연결 리스트는 singly linked list이다. 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재한다.
node의 마지막 요소의 pointer가 null을 가리키면서 list가 끝난다.

class Node {
  constructor (data, next = null) {
    this.data = data,
    this.next = next
  	}
} //node 생성

class LinkedList {
  constructor() {
    this.head = null;
  }
} //linked list 생성

let list = new LinkedList ();

주요 method

• append(데이터): 리스트의 맨 끝에 데이터를 추가.

  let newNode = new Node(data);
  newNode.next = this.head;
  this.head = newNode;

   let tail = this.head;
   while(tail.next !== null){
        tail = tail.next;
   }
   tail.next = newNode;
   return this.head;
}

list (type: object)
head와 tail 변수를 갖고 있으며 구현된 linked list의 처음(head)과 끝(tail) 노드를 가리킨다.

• list.head (type: object)
  head 변수를 담고 있어 나중에 head를 제거할 때 쉽게 사용할 수 있다.

• list.tail (type: object)
  addToTail() 메소드를 사용할 때 가장 끝에 노드를 붙일 때 사용한다.
  head를 통해서 linked list의 tail에 붙이는 방법도 있지만, 이렇게 할 경우에는 노드가 추가로 붙을때 마다 head 부터 끝 노드를 찾는 번거로움(?) 이 필요해진다. (물론 complexity의 차이는 있다.)
  node (type: object)
  Node 객체를 상속 받아서 new node 를 생성 할 때마다 해당 객체를 상속 받게 된다.

• node.value (type: number)
  node를 생성할때 주어진 value 값이 저장된다.

• node.next (type: object)
  다음 노드를 가리키는 값이 저장되어 있으며, 없을 경우에는 null 이다.

• addToTail()
  linked list의 가장 끝(tail)에 새로운 node를 추가할 때 사용할 메소드 이다.
  list.tail을 이용하여 구현한다.

• removeHead()
  linked list의 가장 앞(head)를 삭제할 때 사용할 메소드 이다.
  삭제시에 list.head 을 이용하여 구현 하며 삭제 전 head의 값을 node.next 노드로 변경 한 후 기존 head node를 삭제 해야 한다.

• contains()
  Linked List 로 구현된 객체에서 node.value 가 존재 하는지 확인한다.
  list.head 부터 value 값이 존재하는지 확인해야 하므로 worst case의 경우에는 모든 link를 다 봐야 하는 경우가 생긴다. ( 찾고자 하는 값이 가장 끝 노드에 위치할 경우)
  이러한 경우 때문에 Linked List의 최악의시간복잡도 (O)는 O(n) 이 된다.

• removeAt(위치): 해당 위치에 있는 데이터를 삭제.

• indexOf(데이터): 해당 데이터의 인덱스를 반환. 없을 경우 -1 반환.

• remove(데이터): 데이터를 삭제.

• insert(위치, 데이터): 해당 위치에 데이터를 삽입.

• isEmpty(): 데이터가 하나도 없다면 true를, 그 외엔 false를 반환.

• size(): 데이터 개수를 반환. 배열의 length 프로퍼티와 유사함.