Linked List

Linked List

Linked List(연결 리스트)는 그 크기가 동적인 자료구조로,
노드(자료구조를 구성하는 요소)와 노드의 연결로 이루어진 자료 구조이다.
데이터의 구조들이 일렬로 연결된 구조이며, 각각의 노드는 ‘데이터’와 ‘다음 노드의 정보’를 가지고 있다.
연결 리스트의 맨 처음의 노드를 head, 마지막 노드를 tailtail이라고 한다.

 

위 연결을 코드로 표현하면

LinkedList {head: Node, tail: Node, _size: 4}
head: Node {value: 12, next: Node}
next: Node {value: 6, next: Node}
next: Node {value: 71, next: Node}
next(tail): Node {value: 26, next: null}

 

연결 리스트의 종류

Singly linked list(일방향 연결 리스트)

리스트를 구성하는 각 노드들이 서로 다음 노드를 가리키는 정보를 가지고 있는 연결 리스트

 

Doubly linked list (이중 연결 리스트)

리스트를 구성하는 각 요소들이 이전의 노드와 이후의 노드에 대한 정보를 가지고 있다.

 

시간 복잡도(Time Complexity)

자료구조	가져오기	추가하기	삭제하기
Linked List	O(n)	O(1)	O(1)

 

Linked List 구현을 위한 수도코드

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }

    // 주어진 값을 연결 리스트 끝에 추가하는 메소드
addToTail(value) {
      // Node 클래스를 가지고 새 인스턴스를 생성(value 속성을 가지는)

      // 첫 노드인 경우(이전에 다른 노드가 없음)

      // head는 새 노드
      // tail도 새 노드
      // 사이즈 증가

      // 이전에 다른 노드가 있는 경우

      // 현재 tail의 next에 새 노드를 추가
      // 새 노드가 새로운 tail이 된다.

      // size가 1 증가

    // 주어진 값을 연결 찾아서 연결을 해제하는 메소드
remove(value) {
      // 현재 노드의 head를 새로 선언

      // head의 value가 value와 같다면
      // 기존 head를 다음 노드의 head로 재할당
      // 현재 노드를 새로운 변수에 선언

      // 아니면
      // while 반복문(조건: 현재 노드의 다음 노드까지)
      // 현재 노드의 value가 value와 같다면
      // 이전 노드가 현재 노드로 이동
      // 현재 노드가 다음 노드로 이동

      // 현재 노드의 value가 value와 같지 않다면
      // 이전 노드, 현재 노드 둘 다 재할당되어 계속 돌아감.

      // size가 1 감소

   // 주어진 값의 인덱스를 노드를 반환하는 메소드(없을 경우 undefined 반환)
getNodeAt(index) {

      // 카운트를 담을 변수 선언
      // 현재 노드를 담을 변수 선언
      // while 반복문으로 노드를 돌면서
      // 카운트가 인덱스라면
      // 노드를 리턴

      // 아니라면 카운트가 1증가한다.
      // 노드가 다음 노드로 재할당

      // 반복문 끝나도 안나오면 undefined를 리턴

   // 주어진 값을 가지는 노드의 존재 여부를 반환하는 메소드(boolean)
  contains(value) {
      // 현재 노드를 담을 변수 선언
			// while 반복문으로 node를 돌면서
      // 노드의 value가 value라면
      // true를 리턴

      // 아니면 노드를 다음 노드로 재할당

      // 반복문 끝나도 안나오면 false를 리턴

   // 주어진 값의 인덱스를 반환하는 메소드(없을 경우 -1을 반환)
  indexOf(value) {
      // 현재 노드를 담을 변수 선언
      // 카운트를 담을 변수 선언

      // while 반복문으로 노드를 돌면서
      // 현재 노드의 value가 value와 같을 때까지
      // 같을 때 카운트를 리턴

      // 아니라면 카운트가 1 증가
      // 노드도 다음 노드로 재할당

      // 반복문 끝날 때까지 안나오면 -1를 리턴

   // size를 반환하는 메소드
  size() {
    // size를 리턴