각 노드가 값과 다음 노드의 참조를 저장하는 선형 자료구조입니다. 연속된 메모리가 필요 없고, 삽입과 삭제는 연결만 바꾸지만 특정 위치 접근은 head부터 순차적으로 이동합니다.
노드는 value와 next 참조를 가지며 head부터 순차 접근
1class ListNode {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7 8class LinkedList {9 constructor() {10 this.head = null;11 }12 13 append(value) {14 const newNode = new ListNode(value);15 if (!this.head) {16 this.head = newNode;17 return newNode;18 }19 20 let current = this.head;21 while (current.next) {22 current = current.next;23 }24 current.next = newNode;25 return newNode;26 }27 28 remove(value) {29 if (!this.head) return false;30 if (this.head.value === value) {31 this.head = this.head.next;32 return true;33 }34 35 let current = this.head;36 while (current.next && current.next.value !== value) {37 current = current.next;38 }39 if (!current.next) return false;40 current.next = current.next.next;41 return true;42 }43 44 traverse() {45 let current = this.head;46 while (current) {47 console.log(current.value);48 current = current.next;49 }50 }51}배열 값이 next 참조로 연결되는 과정을 콘솔 출력으로 확인
1// Online Javascript Editor for free2// Write, Edit and Run your Javascript code using JS Online Compiler3 4function ListNode(val) {5 this.val = val;6 this.next = null;7}8 9function createLinkedList(arr) {10 let head = new ListNode(arr[0]);11 let current = head;12 13 for (let i = 1; i < arr.length; i++) {14 current.next = new ListNode(arr[i]);15 console.log('current', current);16 current = current.next;17 }18 19 return head;20}21 22const list = createLinkedList([1, 2, 3, 4, 5]);23 24console.log('list', list);current ListNode { val: 1, next: ListNode { val: 2, next: null } }
current ListNode { val: 2, next: ListNode { val: 3, next: null } }
current ListNode { val: 3, next: ListNode { val: 4, next: null } }
current ListNode { val: 4, next: ListNode { val: 5, next: null } }
list ListNode {
val: 1,
next: ListNode { val: 2, next: ListNode { val: 3, next: [ListNode] } }
}Step
1 / 9