[자료구조]Linked List

Linked List란?

연결리스트는 순차적으로 데이터를 관리하는 배열과 달리 연결리스트는 메모리가 퍼져있는 상태로 포인트가 다음 데이터를 가리키고 있는 구조입니다.

연결리스트의 특징은 메모리가 허용하는한 요소를 제한없이 추가 할 수 있으며, 탐색은 선형 시간[O(n)]이 소요되고 요소를 추가하거나 제거할 때는 상수 시간[O(1)]이 소요됩니다. 연결리스트의 종류는 다음과 같습니다.

• 단일 연결리스트(SinglyLinkedList) -> 데이터 1개, 포인터 1개(다음 노드로 이동)
• 이중 연결리스트(Doubly LinkedList) -> 데이터 1개 포인터가 2개(다음 노드 이동, 이전 노드 이동)
• 환형 연결리스트(Circular Linked List) -> tail 포인터가 head를 가리키는 구조
  

다음은 자바스크립트로 단일 연결리스트를 구현한 코드입니다. 자바스크립트에는 스크립트 코드로 동적으로 배열의 크기가 조정되어 특별하게 구현하게 될 사용할 필요는 없지만 배열의 크기가 정해져있는 다른 언어에서는 연결리스트를 이용하여 배열의 요소를 손 쉽게 다룰 수 있습니다.

단일 연결리스트 구현

//단일 연결리스트 구현하기
class Node {
  constructor(value) {
    this.value = value; // 데이터 값
    this.next = null; // 포인터(다음 노드)
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null; // 첫 노드
    this.tail = null // 마지막 노드
  }

// 노드 찾기
  find(value) {
    let currNode = this.head; // 첫 노드 값을 할당
    while (currNode.value !== value) {
      // 현재 노드 값과 찾는 값 반복 비교
      currNode = currNode.next;
    }
    return currNode;
  }

  // 마지막 노드로 추가
  append(newValue) {
    const newNode = new Node(newValue);
    console.log(newNode)
    if (this.head === null) {
      //  현재 아무 노드도 없는 경우
      this.head = newNode; // 새로만든 노드를 첫번쨰 노드로 한다.
      this.tail = newNode; // 새로만든 노드를 마지막 노드로 한다        
    } else {
      // 기존 요소가 있는 경우
      this.tail.next = newNode; // 현재 마지막 노드가 가리키는 값을 새로만든 노드로 한다.
      this.tail = newNode; // 마지막 노드를 새로운 노드로 한다.
    }
  }

  // 중간 노드로 추가
  insert(node, newValue) {
    const newNode = new Node(newValue); // 새로운 값으로 새로운 노드를 생성한다.
    newNode.next = node.next; // 중간에 추가하려는 위치의 이전노드가 가리키는 노드를 새로만든 노드가 가리키게 한다.
    node.next = newNode; // 기존의 노드는  새로운 노드를 가리킨다.
  }

  // 노드 삭제
  remove(value) {
    let prevNode = this.head; // 첫번째 노드를 prevNode로 생성
    while (prevNode.next.value !== value) {
      // prevNode의 다음  노드들의 값들을 비교한다.
      prevNode = prevNode.next;
    }
    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next; // PrevNode가 다음 노드가 아닌 다음 다음 노드를 가리키게 한다.(가운데 요소는 삭제)
    }
  }

  // 노드 출력
  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;

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


const linkedList = new SinglyLinkedList();
linkedList.append(1); // 첫번째 노드에 1 추가
linkedList.append(5); // 첫번째 노드에 5 추가
linkedList.append(10); // 첫번째 노드에 10 추가
console.log(linkedList.find(5)); // Node {value:5, next: Node {value: 10, next: null}}

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