(TIL Day03-02)자료구조-연결 리스트(1) 단방향 연결 리스트

연결 리스트

• 각 요소를 포인터로 연결하여 관리하는 선형 자료구조.
• 각 요소는 노드라고 부르며, 데이터 영역과 포인터 영역으로 구성된다.
• 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
• 탐색은 O(n)이 소요.
• 요소를 추가하거나 제거할 때는 O(1)이 소요.
• Singly Linked List, Doubly Linked List, Circular Linked List가 존재.

 

---

 

배열과의 차이점

• 배열은 데이터가 메모리에 연속적으로 붙어있지만, 연결 리스트는 붙어있지 않다.
• 원소를 찾기 위해서 배열은 인덱스로 접근이 가능하지만, 연결 리스트는 해당 데이터 영역을 찾아야 한다.(그렇기 때문에 에 시간 복잡도가 서로 상반된다.)

 

 

---

 

Singly Linked List

• 단방향 연결 리스트
• Head에서 Tail까지 단방향으로 이어지는 연결리스트.
• 가장 단순한 형태의 연결 리스트.

Singly Linked List

데이터 추가

• 6과 2 사이에 21을 추가했을 때, 아래와 같이 진행된다.
• 6의 포인터 영역은 새롭게 만든 21을 가리키고, 21은 2를 가리키게 된다.

 

데이터 삭제

• 2를 삭제했을 때, 아래 사진과 같이 진행.
• 21의 포인터 영역을 2의 포인터 영역인 8로 이어준 후, 2를 삭제한다.

 

코드

아래는 Singly Linked List를 코드로 구현한 것이다.

데이터 추가, 삽입, 삭제 과정만 나타냈으며,

직접 눈과 손으로 확인하는 것을 추천!

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  find(value) {
    let currentNode = this.head;

    while (currentNode !== null && currentNode.value != value) {
      currentNode = currentNode.next;
    }

    if (currentNode === null) {
      console.log(`FindError...Can't find the value : ${value}`);
    }

    return currentNode;
  }

  append(value) {
    const newNode = new Node(value);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  insert(node, value) {
    if (node === null) {
      return;
    }

    const newNode = new Node(value);
    newNode.next = node.next;
    node.next = newNode;
    this.size++;
  }

  remove(value) {
    let prevNode = this.head;

    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
      this.size--;
    } else {
      console.log(`RemoveError...Can't find the value : ${value}`);
    }
  }

  display() {
    let currentNode = this.head;
    let displayString = "[";

    while (currentNode !== null) {
      displayString += `${currentNode.value}, `;
      currentNode = currentNode.next;
    }

    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }

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

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(6);
linkedList.append(2);
linkedList.append(8);
linkedList.display();
linkedList.insert(linkedList.find(6), 21);
linkedList.display();
linkedList.remove(2);
linkedList.display();

실행 결과

---