[Data Structure] 더블 링크드 리스트 (이중 연결 리스트, Doubly Linked List, Javascript, python)

더블 링크드 리스트 (Doubly Linked List)

---

이중 연결 리스트, 양방향 링크드 리스트라고 불립니다.

더블 링크드 리스트는 기존 단반향 리스트의 단점을 보완한 자료구조입니다.

노드 (Node)

---

더블 링크드 리스트는 노드를 양방향으로 연결하는 구조입니다.

노드에는 저장할 데이터와 다음 노드를 가리키는 주소 저장 공간, 이전 노드를 가리키는 주소 저장 공간이 있습니다.

연결 리스트 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

구현

---

노드 구현 (javascript, python)

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class Node(object):
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

 링크드 리스트의 추가 기능, 삽입 기능, 삭제 기능, 검색 기능(양방향 모두)을 구현해보겠습니다.

 

링크드 리스트 구현(javascript, python)

class DoublyLinkedList {
  #size = 0;
  #head = null;
  #tail = null;

  getSize() {
    return this.#size;
  }

  printFromHead() {
    const list = [];
    let current = this.#head;
    while (current) {
      list.push(current.data);
      current = current.next;
    }
    console.log(list.toString());
  }

  printFromTail() {
    const list = [];
    let current = this.#tail;
    while (current) {
      list.push(current.data);
      current = current.prev;
    }
    console.log(list.toString());
  }

  add(node) {
    this.#size++;
    if (!this.#head) {
      this.#head = node;
      this.#tail = node;
    } else {
      let current = this.#head;
      while (current.next) current = current.next;
      current.next = node;
      node.prev = current;
      this.#tail = node;
    }
  }

  insertFrontAtData(node, data) {
    let current = this.#tail;
    while (current) {
      if (current.data == data) {
        this.#size++;
        node.next = current;
        node.prev = current.prev;
        current.prev.next = node;
        current.prev = node;
        return;
      } else current = current.prev;
    }
  }

  insertBackAtData(node, data) {
    let current = this.#head;
    while (current) {
      if (current.data == data) {
        this.#size++;
        node.prev = current;
        node.next = current.next;
        current.next.prev = node;
        current.next = node;
        return;
      } else current = current.next;
    }
  }

  removeDataFromHead(data) {
    let current = this.#head;
    if (current?.data == data) {
      this.#size--;
      this.#head = current.next;
      current.prev = null;
    } else {
      while (current) {
        if (current.data == data) {
          this.#size--;
          current.prev.next = current.next;
          current.next.prev = current.prev;
          return;
        } else current = current.next;
      }
    }
  }

  searchFromHead(data) {
    let current = this.#head;
    while (current) {
      if (current.data == data) return current;
      else current = current.next;
    }
    return null;
  }

  searchFromTail(data) {
    let current = this.#tail;
    while (current) {
      if (current.data == data) return current;
      else current = current.prev;
    }
    return null;
  }
}

class DoublyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def printFromHead(self):
        arr = []
        node = self.head
        while node:
            arr.append(node.data)
            node = node.next
        print(arr)

    def printFromTail(self):
        arr = []
        node = self.tail
        while node:
            arr.append(node.data)
            node = node.prev
        print(arr)

    def add(self, node):
        self.size += 1
        if self.head == None:
            self.head = node
            self.tail = self.head
        else:
            current = self.head
            while current.next:
                current = current.next
            node.prev = current
            current.next = node
            self.tail = node

    def insertFrontAtData(self, node, data):
        current = self.tail
        while current:
            if current.data == data:
                self.size += 1
                node.next = current
                node.prev = current.prev
                current.prev.next = node
                current.prev = node
                return
            current = current.prev

    def insertBackAtData(self, node, data):
        current = self.head
        while current:
            if current.data == data:
                self.size += 1
                node.prev = current
                node.next = current.next
                current.next.prev = node
                current.next = node
                return
            current = current.next

    def removeDataFromTail(self, data):
        current = self.tail
        if not current:
            return
        if current.data == data:
            self.size -= 1
            self.tail = current.prev
            current.prev.next = None
        else:
            while current:
                if current.data == data:
                    self.size -= 1
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    return
                else:
                    current = current.prev

    def searchFromTail(self, data):
        if self.tail == None:
            return None
        node = self.tail
        while node:
            if node.data == data:
                return node
            node = node.prev
        return None

    def searchFromHead(self, data):
        if self.head == None:
            return None
        node = self.head
        while node:
            if node.data == data:
                return node
            node = node.next
        return None

더블 링크드 리스트의 장단점

---

• 장점
  • 단방향 링크드 리스트의 단점인 단방향 탐색을 보완
• 단점
  • 구현이 어려움