임의 접근이 불가능하여 특정 위치의 노드를 찾기 위해서는 처음부터 순차적으로 탐색해야 합니다.
각 노드가 추가적인 포인터를 저장하기 때문에 배열보다 메모리 오버헤드가 발생합니다.
< 주요 연산 >
삽입 (Insertion)
리스트의 시작 부분, 중간, 끝 부분에 노드를 삽입합니다.
시작 부분 삽입의 경우: 새 노드의 다음 포인터를 현재 첫 번째 노드를 가리키도록 설정하고, 헤드를 새 노드로 변경합니다.
중간 삽입의 경우: 삽입 위치의 이전 노드와 다음 노드를 각각 새 노드와 연결합니다.
삭제 (Deletion)
특정 위치에 있는 노드를 삭제합니다.
시작 부분 삭제의 경우: 헤드를 현재 첫 번째 노드의 다음 노드로 변경합니다.
중간 삭제의 경우: 삭제할 노드의 이전 노드의 포인터를 삭제할 노드의 다음 노드를 가리키도록 변경합니다.
탐색 (Search)
특정 값을 가지는 노드를 찾기 위해 리스트를 순차적으로 탐색합니다.
출력 (Display)
리스트에 있는 모든 노드를 순차적으로 출력합니다.
반전 (Reverse)
리스트를 반전시킵니다. prev, current, next 포인터를 사용하여 리스트의 노드들을 뒤집습니다.
< 구현 : 단일 링크드 리스트 >
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
}
// 시작 부분 삽입
insertAtBeginning(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
// 중간 삽입
insertAtPosition(data, position) {
if (position === 0) {
this.insertAtBeginning(data);
return;
}
const newNode = new Node(data);
let current = this.head;
let previous = null;
let index = 0;
while (index < position && current !== null) {
previous = current;
current = current.next;
index++;
}
if (current === null) {
console.log("Position out of bounds");
return;
}
newNode.next = current;
previous.next = newNode;
}
// 끝 부분 삽입
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 시작 부분 삭제
deleteAtBeginning() {
if (this.head) {
this.head = this.head.next;
}
}
// 중간 삭제
deleteAtPosition(position) {
if (position === 0) {
this.deleteAtBeginning();
return;
}
let current = this.head;
let previous = null;
let index = 0;
while (index < position && current !== null) {
previous = current;
current = current.next;
index++;
}
if (current === null) {
console.log("Position out of bounds");
return;
}
previous.next = current.next;
}
// 끝 부분 삭제
deleteAtEnd() {
if (!this.head) {
return;
}
if (!this.head.next) {
this.head = null;
return;
}
let current = this.head;
while (current.next && current.next.next) {
current = current.next;
}
current.next = null;
}
// 탐색
search(data) {
let current = this.head;
while (current) {
if (current.data === data) {
return true;
}
current = current.next;
}
return false;
}
// 출력
display() {
let current = this.head;
let listString = '';
while (current) {
listString += current.data + ' -> ';
current = current.next;
}
listString += 'null';
console.log(listString);
}
// 반전
reverse() {
let prev = null;
let current = this.head;
let next = null;
while (current) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
}
}
// 사용 예제
const sll = new SinglyLinkedList();
sll.append(1);
sll.append(2);
