[JavaScript] ListNode (연결리스트 - linked list)

코딩테스트 문제를 풀다보니 ListNode를 사용해야하는 문제를 접하게 되어 다시 정리할 겸 포스팅하려 합니다.

 

ListNode란?

자바스크립트에서 ListNode란 연결 리스트(linked list)의 기초 구성 요소인 노드(node)를 의미해요. 연결 리스트는 배열과 마찬가지로 선형적인 데이터를 다루지만, 배열과는 구조가 다르다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(또는 참조)를 포함하고, 메모리에서 연속적인 위치를 차지하지 않아, 덕분에 데이터의 삽입과 삭제가 효율적이지만, 특정 요소를 검색할 때는 배열보다 느릴 수 있다.

 

ListNode 구현하기

• Node 클래스: 데이터와 다음 노드를 가리키는 포인터를 속성으로 가지는 간단한 클래스입니다.

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

 

• ListNode 사용 예시: 아래와 같이 두 개의 노드를 next로 연결하여 연결 리스트를 형성할 수 있습니다.
  
   

const n1 = { data: 100 };
const n2 = { data: 200 };

n1.next = n2; // n1 노드의 next로 n2 노드를 연결
console.log(n1); // { data: 100, next: { data: 200 } }

 

 

연결 리스트의 이해와 활용

• 기본 개념: 데이터를 선형으로 관리하면서, 각 요소들이 메모리 상에서 연속적인 위치에 있지 않아 삽입과 삭제가 용이합니다.
• 활용: 웹 브라우저의 히스토리 관리 등 순서가 중요한 경우에 사용됩니다.

 

ListNode 사용 예시

• 단일 ListNode 생성: 데이터를 저장하는 노드를 생성하여 그 안에 값을 담을 수 있습니다.

const node1 = { 
  data: 100, 
  next: null // 다음 노드를 참조하는 포인터, 현재는 다음 노드가 없으므로 null
};

• ListNode 연결하기: 다음 노드를 참조하는 포인터를 사용하여 다른 노드와 연결할 수 있습니다.

const node2 = { 
  data: 200, 
  next: null
};

node1.next = node2; // node1의 next로 node2를 연결
console.log(node1); // { data: 100, next: { data: 200, next: null } }

연결 리스트에 데이터 삽입 및 삭제하기

• 데이터 삽입: 기존 노드 사이에 새로운 노드를 넣어서 연결을 갱신하는 과정을 통해 데이터를 쉽게 삽입 가능합니다.

const node3 = { data: 150, next: null };
node3.next = node2; // 새 노드 node3의 next로 node2를 가리킴
node1.next = node3; // node1의 next를 node3으로 변경하여 node2 사이에 node3을 삽입

• 데이터 삭제: 특정 노드를 제거하기 위해선 해당 노드의 이전 노드가 다음 노드를 가리키게하여 연결을 끊으면 됩니다.

node1.next = node2; // node1이 node3을 건너뛰고 node2를 바로 가리키게 하여 node3를 연결 리스트에서 제거