[자료구조&알고리즘] 연결리스트(Linked List)

cojet·2022년 10월 20일

linked list 알고리즘 연결리스트 자료구조

자료구조&알고리즘

목록 보기

4/16

배열이 추가와 제거가 반복되는 로직에서 불리하다면 무엇을 사용해야 할까요?

연결리스트(Linked List)

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조입니다.
각 요소는 노드(node)라고 부르며 데이터 영역과 포인터 영역으로 구성됩니다.

특징

메모리가 허용하는한 요소를 제한없이 추가할 수 있습니다.
탐색은 O(n)이 소요됩니다.
요소를 추가하거나 제거할때 O(1)이 소요됩니다.
Singly Linked List, Doubly Linked List, Circular Linked List가 존재합니다.

메모리 차이

배열의 경우 순차적인 데이터가 들어가기 때문에 메모리의 영역을 연속적으로 사용합니다.
반면, 연결리스트는 데이터가 순차적이지 않기 때문에 메모리의 영역이 불연속적입니다.

➡ 메모리의 영역을 알기 위해 포인터를 사용하여 각 영역을 참조합니다.

배열과 연결리스트의 요소 제거 예시를 보겠습니다.

배열의 경우 제거시 최대 O(n)만큼의 시간 복잡도를 갖습니다.

연결리스트의 경우 제거시 O(1)만큼의 시간 복잡도를 갖습니다.

단일 연결 리스트(Singly Linked List)

단일 연결 리스트는 Head에서 Tail까지 단방향으로 이어지는 연결 리스트로
가장 단순한 형태인 연결 리스트입니다.

노드 찾기

헤드 포인터에서 시작해서 찾고자하는 데이터인지 확인후
찾고자하는 데이터가 아니라면 포인터 영역을 통해 다음 노드로 이동합니다.
해당 요소를 찾을때까지 반복합니다.

노드 추가

'E'를 B와 C사이에 추가해보도록 하겠습니다.

추가할 노드의 포인터 영역을 C데이터를 가진 노드를 가리키도록합니다.
B데이터를 가진 노드의 포인터가 추가할 노드를 가리키도록 합니다.

추가를 위해 탐색을 진행한다면 O(n)의 시간복잡도를 갖기 때문에 주의해야합니다!

노드 삭제

'B'를 삭제해보도록 하겠습니다.

삭제할 노드의 이전 노드가 삭제할 요소의 다음 노드를 가리키게합니다.
삭제할 노드를 삭제합니다.

JavaScript에서 단일 연결 리스트

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

class SinglyLinkedList {
  // 헤드와 테일 포인터로 구성
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  size() {
    console.log(this.length);
  }

  // 찾기 로직
  find(value) {
    let currNode = this.head;
    // 값을 찾을때까지 다음 노드로 넘어감
    while (currNode.value !== value) {
      currNode = currNode.next;
      if (currNode === null) {
        return null;
      }
    }
    return currNode;
  }

  // 마지막에 추가 로직
  append(newValue) {
    // 입력받은 값으로 노드 생성
    const newNode = new Node(newValue);
    // 헤드가 비어있으면 = 연결리스트에 아무런 값이 없음
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
      // 값이 존재한다면, tail의 포인터가 새로 생성된 노드를 가리킴
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // 중간에 삽입 로직
  insert(node, value) {
    // 입력된 노드가 유효한지 체크
    if (node === null) {
      console.log(null);
    } else {
      // 입력된 node가 연결 리스트에 있을때
      const newNode = new Node(value);
      newNode.next = node.next;
      node.next = newNode;
      this.length++;
    }
  }

  // 삭제 로직
  // 값을 찾은후 삭제함 O(n)
  // O(1)의 시간복잡도를 갖기 위해서는 삭제할 노드의 이전노드를 입력받으면 됨
  remove(value) {
    // 삭제할 노드의 이전 노드 탐색
    if (this.find(value) === null) {
      console.log(null);
    } else {
      let prevNode = this.head;
      while (prevNode.next.value !== value) {
        prevNode = prevNode.next;
      }
      // 찾았다면 이전 노드의 다음을 삭제할 노드의 나음 노드를 가리키도록함
      // 삭제할 노드가 아무런 노드와 연결되어있지 않기때문에 삭제됨
      // garbage collector에의해 메모리상에서 제거됨
      if (prevNode.next !== null) {
        prevNode.next = prevNode.next.next;
      }
      this.length--;
    }
  }

  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display(); // [1, 2, 3, 5]

console.log(linkedList.find(3)); // Node { value: 3, next: Node { value: 5, next: null } }

linkedList.remove(3);
linkedList.display(); // [1, 2, 5]

linkedList.insert(linkedList.find(2), 10);
linkedList.display(); // [1, 2, 10, 5]

linkedList.size(); // 4