[Typescript] 자료구조 : 이중 연결 리스트 (doubly-LinkedList)

단방향 연결 리스트에 이어서 이번엔 이중 연결 리스트입니다.

단방향 연결 리스트 개념을 보고 오시는 것이 좋습니다 :)

 

 

[Typescript] 자료구조 : 단방향 연결 리스트 (Singly-LinkedList)

 

 

 

이중 연결 리스트의 모습

 

 

 

이중 연결 리스트의 특징

• 탐색 시, O(n) 만큼 소요됩니다.
• 추가, 삭제 시, O(1) 만큼 소요됩니다.
• 메모리 상으로 인접하지 않은 데이터들을 연결할 수 있습니다. (공간 효율성이 뛰어남)

* 단방향 연결 리스트와 특징이 유사합니다.

 

 

 

단방향 연결 리스트와의 차이점

• 이전 노드(prev) 를 참조할 수 있습니다.
• 정방향으로 모든 노드를 순회할 수 있고, 역방향으로도 모든 노드를 순회할 수 있습니다. (prev가 있기 때문)
• 다음 노드(next)의 위치를 잃어버려도, 이전 노드(prev)를 기억하고 있으면 데이터 손실을 방지할 수 있습니다.
• 단방향 연결 리스트에 비해 자료구조 크기가 크고, 구현 로직이 복잡합니다.

 

 

 

데이터 노드 구현하기

class Node {
    value: number;
    prev: Node | null = null;
    next: Node | null = null;

    constructor(value: number) {
      this.value = value;
    }
  }

prev, next 프로퍼티가 있습니다.

value 프로퍼티로 데이터를 받고 있고, 숫자 데이터만 받기로 정했습니다.

 

 

 

 

이중 연결 리스트 틀 잡기

class doublyLinkedList {
    private head: Node = null;
    private tail: Node = null;
    private size: number = 0;

    isEmpty() { ... }

    traverse() { ... }

    traverseBack() { ... }

    insertFront(node: Node) { ... }

    insertBack(node: Node) { ... }

    insertAt(idx: number, node: Node) { ... }

    removeFront() { ... }

    removeBack() { ... }

    removeAt(idx: number) { ... }
}

 

 

프로퍼티

• head : 첫 노드를 참조합니다.
• tail : 마지막 노드를 참조합니다.
• size : 노드의 갯수입니다.

 

메소드

* 총 9개의 메소드를 제공하려고 합니다.

* 노드의 인덱스(idx)는 0부터 시작합니다.

• isEmpty : 연결 리스트가 비었는지 체크합니다.
• traverse : 연결 리스트를 정방향으로 순회합니다. (head 노드부터)
• traverseBack : 연결 리스트를 역방향으로 순회합니다. (tail 노드부터)
• insertFront : 맨 앞에 노드를 추가합니다.
• insertBack : 맨 뒤에 노드를 추가합니다.
• insertAt : 인덱스 위치에 노드를 추가합니다.
• removeFront : 맨 앞의 노드를 삭제합니다.
• removeBack : 맨 뒤의 노드를 삭제합니다.
• removeAt : 인덱스 위치의 노드를 삭제합니다.

 

 

 

isEmpty 메소드 구현

isEmpty() {
  return this.size === 0;
}

 

 

 

 

탐색 메소드 (traverse, traverseBack) 구현

// traverse
traverse() {
    if (this.isEmpty()) {
        console.log("null");
        return;
    }

    let current = this.head;
    let result = current.value + "";

    while (current.next) {
        current = current.next;
        result += " <-> " + current.value;
    }

    result += " -> null";
    console.log(result);
}


// traverseBack
traverseBack() {
    if (this.isEmpty()) {
        console.log("null");
        return;
    }

    let current = this.tail;
    let result = current.value + "";

    while (current.prev) {
        current = current.prev;
        result += " <-> " + current.value;
    }

    result += " -> null";
    console.log(result);
}

 

 

 

 

삽입 메소드 (insertBack, insertFront, insertAt) 구현

// insertFront
insertFront(node: Node) {
    if (this.isEmpty()) {
        this.head = node;
        this.tail = node;
    } else {
        const secondNode = this.head;

        node.next = secondNode;
        secondNode.prev = node;

		this.head = node;
	}

	this.size++;
}

// insertBack
insertBack(node: Node) {
    if (this.isEmpty()) {
        this.head = node;
        this.tail = node;
    } else {
        const tailPrevNode = this.tail;

        tailPrevNode.next = node;
        node.prev = tailPrevNode;

        this.tail = node;
    }

	this.size++;
}

// insertAt
insertAt(idx: number, node: Node) {
    if (idx < 0 || idx > this.size) {
        console.log("index error!");
        return;
    }

    if (idx === 0) {
        this.insertFront(node);
        return;
    }

    if (idx === this.size) {
        this.insertBack(node);
        return;
    }

    // 중간노드 삽입
    let current = this.head;
    let currentIdx = 0;

    while (idx !== currentIdx) {
        current = current.next;
        currentIdx++;
    }

    node.next = current;
    node.prev = current.prev;
    current.prev.next = node;
    current.prev = node;

    this.size++;
}

 

 

 

 

삭제 메소드 (removeBack, removeFront, removeAt) 구현

// removeFront
removeFront() {
    if (this.isEmpty()) {
        console.log("list is empty!");
        return;
    }

    if (!this.head.next) {
        this.head = null;
        this.tail = null;
        this.size = 0;
    	return;
    }

    const secondNode = this.head.next;

    this.head = secondNode;
    secondNode.prev = null;

    this.size--;
}

// removeBack
removeBack() {
    if (this.isEmpty()) {
        console.log("list is empty!");
        return;
    }

    if (!this.tail.prev) {
        this.head = null;
        this.tail = null;
        this.size = 0;
	    return;
    }

    const tailPrevNode = this.tail.prev;

    this.tail = tailPrevNode;
    tailPrevNode.next = null;

    this.size--;
}

// removeAt
removeAt(idx: number) {
    if (idx < 0 || idx > this.size - 1) {
	    console.log("index error!");
    	return;
	}

    if (idx === 0) {
        this.removeFront();
        return;
    }

    if (idx === this.size - 1) {
        this.removeBack();
        return;
    }

    // 중간노드 제거
    let current = this.head;
    let currentIdx = 0;

    while (idx !== currentIdx) {
        current = current.next;
        currentIdx++;
    }

    current.prev.next = current.next;
    current.next.prev = current.prev;
    current.prev = null;
    current.next = null;

    this.size--;
}

 

 

 

 

구현한 코드를 테스트 해보기

// Test
const list = new doublyLinkedList();

list.insertBack(new Node(1));
list.insertBack(new Node(2));
list.insertBack(new Node(3));

list.removeAt(2);

list.traverse();
list.traverseBack();

 

console 출력값

1 <-> 2 -> null
2 <-> 1 -> null