JavaScript에서 연결된 목록 구현

Jan 13 2023

연결된 목록은 데이터가 단일 메모리 위치에 저장되지 않는다는 사실을 제외하면 배열과 매우 유사한 데이터 구조입니다. JavaScript에서 연결된 목록의 각 요소(노드)는 마지막 요소가 아무것도 가리키지 않을 때까지(연결된 목록의 끝) 연결 목록의 다음 요소를 가리키는 다음 요소(노드)를 가리키는 객체입니다. .

연결 리스트의 진입점을 헤드라고 합니다. 헤드는 연결된 목록의 첫 번째 노드에 대한 참조입니다. 목록의 마지막 노드는 null을 가리킵니다. 목록이 비어 있으면 헤드는 null 참조입니다.

그림으로 가장 잘 보이는 연결 목록은 다음과 같습니다.

이것은 또한 다음과 같이 볼 수 있습니다.

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

음악 플레이어 — 음악 플레이어의 노래가 이전 노래와 다음 노래에 연결됩니다. 따라서 목록의 시작 또는 끝에서 노래를 재생할 수 있습니다.
이미지 뷰어 — 이전 및 다음 이미지가 연결되어 있으며 다음 및 이전 버튼으로 액세스할 수 있습니다.
웹 브라우저의 이전 페이지와 다음 페이지 — 링크드 리스트로 연결되어 있기 때문에 뒤로 버튼과 다음 버튼을 눌러 웹 브라우저에서 검색한 이전 URL과 다음 URL에 접근할 수 있습니다.

연결 리스트에는 단일 연결 리스트, 이중 연결 리스트, 순환 연결 리스트의 세 가지 주요 종류가 있습니다. 이 학습의 목적을 위해 Singly Linked List를 구현할 것입니다.

앞에서 언급했듯이 연결 목록은 단순히 서로를 가리키는 요소(노드)의 조합입니다. 연결 리스트의 기본 단위는 노드입니다. 노드는 데이터와 다음 노드에 대한 포인터를 수용하며 다음과 같이 구현됩니다.

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

연결된 목록에서 노드를 제거하는 것은 해당 포인터를 제거하여 구현됩니다. 즉, (제거할) 노드를 가리키는 이전 노드는 (제거할) 노드를 건너뛰고, 따라서 다음 노드를 가리킵니다.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

Linked list와 그 구현을 이해하는 데 도움이 되었기를 바랍니다.

추가 설명이 필요한 경우 LinkedIn에서 저에게 연락할 수 있습니다.https://www.linkedin.com/in/joshua-ajagbe/또는 [email protected] 으로 이메일을 보내주세요 .