[Data Structure] 링크드 리스트 (연결 리스트, Linked List, Javascript, Python)

링크드 리스트 (Linked List)

---

우리말로 연결 리스트라고 부르기도 합니다.

링크드 리스트는 기본적인 배열처럼 데이터가 연결되어 나열하는 구조입니다.

하지만 우리가 아는 배열은 하나의 타입으로만 나열할 수 있지만 링크드 리스트는 노드라고 불리는 데이터 저장 단위로 연결된 구조이기 때문에 다양한 데이터 타입으로 구현이 가능합니다.

(인터프린터 언어인 자바스크립트와 파이썬은 기존 자료형인 Array, list로 링크드 리스트처럼 사용 가능)

노드 (Node)

---

링크드 리스트는 노드를 연결하는 구조입니다.

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

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

위 사진은 연결 리스트의 구조입니다.

노드는 두 개의 저장 공간으로 보라색은 데이터, 파란색은 다음 노드를 가리킵니다.

구현

---

노드 구현 (javascript, python)

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

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

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

 

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

class LinkedList {
  #size = 0;
  #head = null;

  getSize() {
    return this.#size;
  }
  print() {
    const list = [];
    if (!this.#head) console.log(list.toString());
    else {
      let node = this.#head;
      while (node) {
        list.push(node.data);
        node = node.next;
      }
      console.log(list.toString());
    }
  }

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

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

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

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

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

    def printList(self):
        arr = []
        current = Node
        if self.head != None:
            current = self.head
            while current:
                arr.append(current.data)
                current = current.next
        print(arr)

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

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

    def searchData(self, data):
        if self.size != 0:
            current = self.head
            while current:
                if current.data == data:
                    return current
                current = current.next
            return None
        return None

    def removeData(self, data):
        if self.size != 0:
            node = self.head
            if node.data == data:
                self.head = node.next
                self.size -= 1
                return
            while node.next:
                if node.next.data == data:
                    node.next = node.next.next
                    self.size -= 1
                    return
                node = node.next

링크드 리스트의 장단점

---

• 장점
  • 배열 자료형처럼 미리 공간을 할당하지 않아도 됨
  • 다양한 자료형으로 노드에 저장해서 리스트를 구현할 수 있음
• 단점
  • 구현이 어려움
  • 탐색 효율에 큰 차이가 없음
  • 좀 더 복잡한 자료구조 형태로 단점을 극복해야 함