✍ Linked List란..

Linked list (연결 리스트)는 선형 자료구조의 하나로 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 공간적인 효율성을 극대화시킨 자료 구조이다

• 노드 또는 Vertex : 데이터를 담고 있는 그릇. 주로 class로 구현되기 때문에 class라고 생각하도 상관 없다.
• 링크 : 리스트의 순서를 유지할 수 있게 해주는 연결고리이다.
• head : 리스트의 시작 노드를 뜻합니다.
• tail : 리스트의 마지막 노드를 뜻합니다.

📝 Linked List의 특징

1. 직렬적 접근 : 특정 노드에 접근하기 위해서는 head 또는 tail에서부터 시작해 그 위치까지 접근해야 한다.

2. 추가 및 삭제 : 노드의 추가 및 삭제가 쉽다.

3. 비효율적인 메모리 관리 : 각 각의 노드는 연결리스트 특성 상 다음 노드의 정보를 가지고 있어야 하기 때문에 메모리 관리 부분에서는 비효율적이다.

✍ Linked List의 종류

📝 싱글 연결 리스트

노드 끼리 단방향으로 연결되어 있는 리스트로써, next 포인터만 존재합니다.

싱글 연결 리스트 관련 내용으로 최근에 알고리즘 문제를 풀었었는데 그걸 기준으로 한 번 설명해보겠다.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var mergeTwoLists = function(list1, list2) {
    let mergedHead = new ListNode();
    let current = mergedHead;

    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }

    current.next = (list1 === null) ? list2 : list1;

    return mergedHead.next;
};

이미 주어진 알고리즘에서는 싱글 연결 리스트가 구성이 되어 있는데, 보면 현재 값을 출력하는 this.val과 그 다음 포인터를 가리키는 this.next만 존재하는 것으로 알 수 있다.

📝 이중 연결 리스트

그림과 같이 노드 끼리 양방향으로 연결되어 있는 리스트

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  append(value) {
    const node = new Node(value, this.tail);
    if (!this.head) {
      this.head = node;
    }
    if (this.tail) {
      this.tail.next = node;
    }
    this.tail = node;
    this.length++;
  }

  prepend(value) {
    const node = new Node(value, null, this.head);
    if (!this.tail) {
      this.tail = node;
    }
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
    this.length++;
  }

  remove(node) {
    if (node.prev) {
      node.prev.next = node.next;
    } else {
      this.head = node.next;
    }
    if (node.next) {
      node.next.prev = node.prev;
    } else {
      this.tail = node.prev;
    }
    this.length--;
  }
}

📝 원형 이중 연결 리스트

이중 연결 리스트와 비슷하지만 리스트의 마지막에서 next로 넘어갈 시 헤드 노드를 가리키는 리스트

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

class CircularDoublyLinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      this.head.prev = this.head;
      this.head.next = this.head;
    } else {
      const tail = this.head.prev;
      tail.next = node;
      node.prev = tail;
      node.next = this.head;
      this.head.prev = node;
    }
    this.length++;
  }

  prepend(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      this.head.prev = this.head;
      this.head.next = this.head;
    } else {
      const tail = this.head.prev;
      node.next = this.head;
      this.head.prev = node;
      node.prev = tail;
      tail.next = node;
      this.head = node;
    }
    this.length++;
  }

  remove(node) {
    if (this.length === 1) {
      this.head = null;
    } else {
      node.prev.next = node.next;
      node.next.prev = node.prev;
      if (node === this.head) {
        this.head = node.next;
      }
    }
    this.length--;
  }
}

✍️ Linked List vs Array List

지난 번에 Array List에 대해서 언급했을 때도 Lined List와의 차이점에 대해서 간단하게 짚고 넘어갔었지만 이번에 Linked List를 알게 되었으니 확실하게 비교해보자.

1. Array는 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. Linked List도 데이터를 논리적 순서에 따라 데이터를 입력하지만 물리적 주소는 순차적이지 않다.

2. Array는 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근 속도가 매우 빠르다 (indexing). 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있다. 그럼으로 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능함으로 Array에 비해 원하는 데이터에 접근 하는 속도가 떨어진다.
   => Accessbility : Array Wins!

3. Array 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문에 데이터의 삽입/삭제에는 취약한 반면, Linked List는 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 훨씬 쉽다.
   => Insert | Delete : Linked List Wins!

4. 동일한 양의 데이터를 저장해도 일반적으로 연결 리스트가 배열보다 더 많은 메모리를 차지하게 된다 (Array는 단순 데이터 저장인데 비해 Linked List는 각 노드마다 객체를 생성해야 함으로).
   => Memory : Array Wins!

📝 Trade Off (트레이드 오프)

트래이드 오프는 어떤 특성이 좋아지면 다른 특성이 나뻐지는 상황을 의미합니다.

여기서는 Linked List와 Array List는 대표적인 트레이드 오프라고 할 수 있습니다.

✍️ Linked List의 시간 복잡도

• 접근 : O(n)
• 탐색 : O(n)
• 삽입 : O(1) (Best Case)
• 삭제 : O(1) (Best Case)

시간 복잡도는 프로그래머들이 설계한 로직과 데이터 구조에 따라 달라질 수 가 있다. 그렇기 때문에 모든 상황을 고려해서 작성해 놓을 수 없기에 여기에는 내가 찾은 값만 내 기준에 맞춰 작성해보려고 하니 참고 부탁드립니다.

Linked List의 경우에도 시간복잡도 삽입과 삭제의 경우, 단일 연결 리스트에서는 O(n)의 결과를 뿜어낼 수도 있다. 하지만 단일이 아닌 이중 혹은 단일 이라고 해도 경우에 따라 O(1) ~ O(n)이 나올 수 있다는 점을 알아 두었으면 좋겠다.