Linked List, 연결 리스트란?

O(N)의 시간복잡도를 가진 선형적 데이터 구조로 배열과 유사하지만
각 요소가 독립적인 객체에 가까운 자료구조로 요소를 유연하게 삽입, 삭제할 수 있다.
또한 각 요소가 메모리 공간의 흩어져 저장되기 때문에 메모리를 효율적으로 사용할 수 있다.

	연결 리스트(Linked List)	배열(Array)
조회시 시간복잡도	O(N) → 해당 노드까지 순차탐색	O(1) → 인덱스로 조회 가능
삽입, 삭제시 시간복잡도	O(1) → 헤드 삭제 및 추가
O(N) → 중간 요소 삭제 및 추가	O(N) → 모든 요소를 옮겨야 하는 경우

데이터의 삽입, 삭제가 많은 경우 연결리스트 사용, 데이터의 접근이 많은 경우 배열 사용이 적합

연결 리스트의 각 요소를 노드(node) 라고 하는데,
노드는 일반적으로 2가지로 구성된다.

일반적인 데이터
다음 노드를 가리키는 링크

연결 리스트의 첫번째 노드를 헤드(head)라고 부르고 마지막 노드는 null을 가리킨다.
따라서 연결 리스트가 비어있는 경우 헤드는 null을 참조하게 된다.

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

// 함수
function node(value, next) {
  this.value = (value===undefined ? 0 : value)
  this.next = (next===undefined ? null : next)
}
 
// 클래스(ES6)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

연결 리스트의 장점과 단점

장점

데이터 구조의 큰 틀을 바꾸지않고 노드를 추가하거나 삭제하기 쉽다.

단점

탐색이 느리다. O(N)
배열과 O(1) 는 달리 무작위 접근 할 수 없고 순차적으로 접근해야 한다.
각 노드는 포인터(링크)를 담고 있기 때문에 배열보다 더 많은 메모리를 사용한다.

연결 리스트의 유형

1. 단일 연결 리스트(Singly Linked Lists)

각 노드는 하나의 포인터만 가진다.

2. 이중 연결 리스트(Doubly Linked Lists)

각 노드는 2개의 포인터를 가진다.
각각 다음 노드와 이전 노드를 가리킨다.

3. 원형 연결 리스트(Circular Linked Lists)

마지막 노드의 포인터가 첫 노드(헤드) 또는 특정 노드를 가리킨다.

연결 리스트 구현 방법 (JavaScript)

노드와 연결리스트는 다음과 같이 간단하게 구현할 수 있다.

// node 구현
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
 
// Linked List 구현
class LinkedList {
	constructor(head = null) {
		this.head = head;
	}
}
 
// 두개의 node 생성
let node1 = new Node(2);
let node2 = new Node(5);
node1.next = node2 // node1.next는 node2의 메모리 주소를 가리킨다.(객체를 참조)
 
// 생성한 node1을 head로 하는 Linked List 생성
const linkedList = new LinkedList(node1);
 
// Linked List 호출
console.log(linkedList.head.next.value)
// head(2).next(5).value
// 5

연결 리스트 메소드 구현 (JavaScript)

size()

연결 리스트에 있는 노드들의 개수를 반환한다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
 
class LinkedList {
  constructor() {
    this.head = null;
  }
 
	// size(): 연결 리스트에 있는 노드들의 개수를 반환한다.
	size() {
		let count = 0;
		let node = this.node;
		
		while (node) {
			count++;
			node = node.next;
		}
		
		return count;
	}
	
	// clear(): 연결 리스트를 비운다.
	clear() {
		this.head = null;
	}
	
	// getFirst(): 연결 리스트의 첫번째 노드를 반환한다.
	getFirst() {
		return this.head;
	}
	
	// getLast(): 연결 리스트의 마지막 노드를 반환한다.
	getLast() {
		let lastNode = this.head;
		
		if (lastNode) {
			while (lastNode.next) {
				lastNode = lastNode.next;
			}
		}
		
		return lastNode;
	}
	
	// find(): 특정 값을 갖고 있는 노드를 반환한다.
	finde(target) {
		let currentNode = this.head;
		
		while (currentNode) {
			if (currentNode.value !== target) {
				return currentNode;
			}
			
			currentNode = currentNode.next;	
		}
		
		return -1;
	}
	
	// append(): 연결 리스트의 마지막에 노드를 추가한다.
	append(value) {
		const newNode = new Node(value);
		
		if (this.head === null) {
			this.head = newNode;
		} else {
			let lastNode = this.head;
			
			while (lastNode.next) {
				lastNode = lastNode.next;
			}
			
			lastNode.next = newNode;
		}
	}
	
	// insert(): 연결 리스트의 특정 노드 다음에 새로운 노드를 추가한다.
	insert(targetNode, newValue) {
		const newNode = new Node(newValue);
		
		newNode.next = targetNode.next;
		targetNode.next = newNode;
	}
	
	// remove(value): 특정 값을 갖고 있는 노드를 삭제한다.
	remove() {
		if (this.head.value === value) {
			this.head = this.head.next;
		} else {
			let prevNode = this.head;
			
			while (prevNode.next.value !== value) {
				prevNode = prevNode.next
			}
			
			if (prevNode.next !== null) {
				prevNode.next = prevNode.next.next;
			}
		}
	}
}