Linked List

여러 노드들이 연결되어 선형 데이터 구조를 가진다.

각각의 노드는 데이터(data) 필드와 다음 노드에 대한 참조(link)를 포함하는 노드로 구성된다.
노드는 link를 통해 다음 노드를 접근할 수 있으며, 노드들은 다음에 올 노드의 정보를 갖고 있다.

Linked List에서 맨 앞을 Head라고 하며, 맨 마지막을 Tail이라고 한다.

배열이 아닌 Linked List를 사용하는 이유?

배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한사항이 있다.

• 배열은 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 한다.
• 새로운 요소를 삽입하는 것은 비용이 많이 든다. (공간을 새로 만들어야하고, 삽입 될 때마다 기존 요소가 전부 이동해야한다.)

장점

• 동적으로 메모리 사용 가능하다.
• 삽입과 삭제가 용이하다.

단점

• 임의로 접근을 허용할 수 없다. 즉, 첫 번째 노드부터 순차적으로 요소에 접근해야한다.
  => 특정 위치 데이터 검색이 느리다.
• 다음 노드에 대한 주소를 저장해야 되므로 메모리를 추가적으로 사용해야한다.

구현

class Node{
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.head = new Node("head");
    }
  	// 맨 앞 노드에 새로운 노드를 추가
  	prepend(newElement){
      let newNode = new Node(newElement);
      let currNode = this.head;
      newNode.next = currNode.next;
      currNode.next = newNode;
    }
  
  	// 맨 마지막 노드에 새로운 노드를 추가
  	append(newElement) {
		let newNode = new Node(newElement);
      	let currNode = this.head;
      	while(currNode.next != null) {
        	currNode = currNode.next;
        }
      	currNode.next = newNode;
    }
  	
  	// 찾고 싶은 노드를 처음부터 순회해서 있으면 보여줌
    find(item) {
        let currNode = this.head;
        while(currNode.element !== item){
            currNode = currNode.next;
        }
        return currNode;
    }
  
  	// (새로운 노드, 추가하고 싶은 위치) 추가하고 싶은 부분에서 새로운 노드를 추가
    insert(newElement, item) {
        let newNode = new Node(newElement);
        let current = this.find(item);
        newNode.next = current.next; // 추가된 노드가 현재 노드가 가리켰던 곳을 가리킴
        current.next = newNode; // 현재 노드는 추가된 노드를 가리킴
    }
  
  	// 현재 연결되어 있는 노드를 순차적으로 보여줌
    display() {
        let currNode = this.head;
        while(currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
  
  	// 원하는 값의 이전 노드를 찾아서 보여줌
    findPrevious(item) {
        let currNode = this.head;
        while((currNode.next !== null) && (currNode.next.element != item)) {
            currNode = currNode.next;
        }
        return currNode;
    }
  
  	// 원하는 노드를 삭제
    remove(item) {
        let prevNode = this.findPrevious(item);
        if(prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    }
  
  	toString() {
		let array = [];
      	let currNode = this.head;;
      	while(currNode.next !== null) {
			array.push(currNode.next.element);
          	currNode = currNode.next;
        }
      	return array;
    }
}

const test = new LinkedList();
test.insert("A", "head"); //  head -> A
test.insert("B", "A"); // head -> A -> B
test.insert("C","B"); // head -> A -> B -> C
test.insert("1","A"); // head -> A -> 1 -> B -> C
test.append("D"); // head -> A -> B -> C -> D
test.remove("1"); 
test.prepend("1");
test.display(); // haed -> 1 -> A -> B -> C -> D
test.findPrevious("B"); // Node {element: 'A', next: Node}
test.toString(); // ["1", "A", "B", "C", "D"]

이렇게 한쪽 방향으로만 노드를 추가, 삭제, 삽입, 검색을 하는 Linked List를 구현해봤다.

양방향 Linked List

양방향 Linked List는 노드가 앞(prev), 뒤(next)로 접근할 수 있어서 말 그대로 양쪽 방향으로 접근할 수 있는 것을 말한다.

구현

class Node{
    constructor(element) {
        this.element = element;
        this.next = null;
        this.prev = null; // 추가
    }
}
class LinkedList {
    constructor() {
        this.head = new Node("head");
    }
    prepend(newElement) {
        let newNode = new Node(newElement);
        let currNode = this.head;
      	// 변경된 부분
        newNode.next = currNode.next;
        newNode.prev = currNode;
        currNode.next.prev = newNode;
        currNode.next = newNode;
    }
  	append(newElement) {
        let newNode = new Node(newElement);
        let currNode = this.head;
        while(currNode.next !== null) {
            currNode = currNode.next;
        }
        currNode.next = newNode;
        newNode.prev = currNode; // 추가된 부분
    }
    find(item) {
        let currNode = this.head;
        while(currNode.element !== item){
            currNode = currNode.next;
        }
        return currNode;
    }
    insert(newElement, item) {
        let newNode = new Node(newElement);
        let current = this.find(item);
      	// 변경된 부분
        if(current.next === null) {
            newNode.next = null;
            newNode.prev = current;
            current.next = newNode;
        }else {
            newNode.next = current.next;
            newNode.prev = current;
            current.next.prev = newNode;
            current.next = newNode;
        }
    }
    display() {
        let currNode = this.head;
        while(currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
    remove(item) {
        let currNode = this.find(item);
      	// 변경된 부분
        if(currNode.next !== null) {
            currNode.prev.next = currNode.next;
            currNode.next.prev = currNode.prev;
            currNode.next = null;
            currNode.prev = null;
        }
    }
	
  	// 마지막 노드를 처음부터 순회해서 찾아줌
    findLast() {
        let currNode = this.head;
        while(currNode.next !== null) {
            currNode = currNode.next;
        }
        return currNode;
    }
	
  	// 마지막 노드부터 맨 앞까지 반대로 출력해줌
    disReverse() {
        let currNode = this.head;
        currNode = this.findLast();
        while(currNode.prev !== null){
            console.log(currNode.element);
            currNode = currNode.prev;
        }
    }
            
  	toString() {
		let array = [];
      	let currNode = this.head;
      	while(currNode.next !== null) {
			array.push(currNode.next.element);
          	currNode = currNode.next;
        }
      	return array;
    }
}

const test = new LinkedList();
test.insert("A", "head"); //  head -> A
test.insert("B", "A"); // head -> A -> B
test.insert("C","B"); // head -> A -> B -> C
test.insert("1","A"); // head -> A -> 1 -> B -> C
test.prepend("0"); // head -> 0 -> A -> 1 -> B -> C
test.disReverse(); // C -> B -> 1 -> A -> 0
test.toString(); // ['0', 'A', '1', 'B', 'C']

양방향 Linked List에서는 prev가 추가되면서 prepend, append, insert, remove이 변경되었고 findLast, disReverse 부분이 추가되었다. 특히 insert와 remove를 잘 봐야한다.

양방향 Linked List는 각 노드별로 이전과 다음 부분을 고려해서 코드를 구성해야 하기 때문에 메모리 저장공간이 더 필요하다는 단점이 있다.

원형 Linked List

원형 Linked List는 노드의 next가 null을 가리키는 것이 아니라 head노드를 다시 가리켜서 순환구조를 갖는 Linked List다.

구현

class Node{
    constructor(element) {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}
class LinkedList {
    constructor() {
        this.head = new Node("head");
        this.head.next = this.head; // 추가
    }
    find(item) {
        let currNode = this.head;
        while(currNode.element !== item){
            currNode = currNode.next;
        }
        return currNode;
    }
    insert(newElement, item) {
        let newNode = new Node(newElement);
        let current = this.find(item);
      	// 변경된 부분
        if(current.next === null) {
            newNode.next = null;
            newNode.prev = current;
            current.next = newNode;
        }else {
            newNode.next = current.next;
            newNode.prev = current;
            current.next.prev = newNode;
            current.next = newNode;
        }
    }
    display() {
        let currNode = this.head;
        while(currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
    remove(item) {
        let currNode = this.find(item);
      	// 변경된 부분
        if(currNode.next !== null) {
            currNode.prev.next = currNode.next;
            currNode.next.prev = currNode.prev;
            currNode.next = null;
            currNode.prev = null;
        }
    }
}

const test = new LinkedList();
test.insert("A", "head"); //  head -> A
test.insert("B", "A"); // head -> A -> B
test.insert("C","B"); // head -> A -> B -> C
test.insert("1","A"); // head -> A -> 1 -> B -> C
console.log(test.head.next.element); // A
console.log(test.head.prev.element); // C

항상 눈으로 보기만하고 직접 구현해보진 않았는데, 직접 구현해보니 이해하는데 도움이 되었다!

이해가 안되거나 잘 모르겠으면 직접 만들어보는 것이 좋은 것 같다.

참고

[자료구조] 연결리스트 with Javascript
ES6 자료구조 연결리스트(LinkedList) 구현하기(이중연결리스트, 원형연결리스트) 그리고 의문점..
Linked List
javascript-algorithms-linkedList