[JavaScript] Singly Linked List

Linked List

연결 리스트는 각 노드가 다음 노드에 대한 참조를 갖는 자료구조를 말한다.

• 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.

• 각 노드는 data와 다음 노드를 가리키는 포인터로 이루어져있다.

Array vs Linked List

배열에서는 "순서"가, 연결리스트에서는 "관계"가 중요하다.

1. Array

(1) 시간 복잡도

• 삽입 / 삭제
  • 배열의 맨 앞에 삽입/삭제하는 경우 : O(n)
  • 배열의 중간에 삽입/삭제 하는 경우 : O(n)
  • 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
• 탐색 : O(1)

(2) 장점

• 인덱스를 통해 임의의 원소에 접근이 가능하다.

(3) 단점

• 원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모든 원소들을 한 칸씩 밀거나 당겨야 한다.
• 배열의 크기가 고정적이다.
• 연속된 메모리를 사용하기 때문에 중간에 데이터가 삭제되면 공간 낭비가 발생할 수 있다.

(4) 언제 사용할까?

• 검색을 해야할 때
• 데이터의 삽입과 삭제가 적을 때
• 데이터의 개수가 확실하게 정해져 있을 때

2. LinkedList

(1) 시간 복잡도

• 삽입 / 삭제
  • 리스트의 head/tail에 삽입/삭제하는 경우 : O(1)
  • 리스트의 중간에 삽입/삭제 하는 경우 : O(n)
• 탐색 : O(n)

(2) 장점

• 삽입과 삭제가 용이하다 (변화가 일어나는 위치의 앞 뒤 노드 관계만 변경해주면 된다).
• 삽입/삭제시 리스트의 크기가 동적으로 변경된다.

(3) 단점

• 인덱스 접근이 불가능하다.

(4) 언제 사용할까?

• 삽입과 삭제가 자주 일어날 때
• Queue와 같이 FIFO(First-in, First-out) 방식의 자료구조를 구현할 때

코드 구현해보기

function LinkedList() {
	const list = {};
    
    list.head = null;
    list.tail = null;
    list.length = 0;
};

function createNode(value) {
	const node = {};
    
    node.value = value;
    node.next = null;
    
    return node;
};

1. addToTail()

LinkedList.prototype.addToTail = function(value) {
	const node = createNode(value);
    
    if (!this.head) {
    	this.head = node;
        this.tail = node;
    } else {
    	const temp = this.tail;
        temp.next = node;
        this.tail = node;
    }
    
	this.length++;    
};

2. removeHead()

LinkedList.prototype.removeHead = function() {
	if (!this.head) return null;
    
    const temp = this.head;
    if (this.length === 1) {
    	this.head = null;
        this.tail = null;
    } else {
    	this.head = temp.next
    }
    
    this.length--;
    return temp.value;
};

3. contains()

LinkedList.prototype.contains = function(target) {
	let currentNode = this.head;
    
    while (currentNode) {
    	if (currentNode.value === target) {
        	return true;
        }
        currentNode = currentNode.next;
    }
    return false;
};

4. reverse()

LinkedList.prototype.reverse = function() {
	let node = this.head;
    this.head = this.tail;
    this.tail = node;
    
    let prev = null;
    let next = null;
    
    while (node !== null) {
    	next = node.next;
    	node.next = prev;
        prev = node;
        node = next;
    }
};