링크드 리스트

Published: Jan 21, 2020 by Dev-hwon

링크드 리스트 (Linked List)

연결 리스트라고도 함
값과 다음 노드에 대한 포인터(참조)가 포함된 노드로 이루어진 선형 리스트
떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
마지막 노드는 null 값(파이썬에서는 None)
스택(새 항목을 헤드에 추가)과 큐(새 항목을 테일에 추가)를 구현 가능
런타임에 저장할 항목의 수를 알 수 없을 때 유용
시간복잡도
- 삽입 : \(O(1)\)
- 검색 및 삭제 : \(O(n)\)
- 뒤부터 순회하거나 정렬하는 최악의경우 : \(O(n^2)\)
- 어떤 노드의 포인터를 알고 있을 때 삭제 : \(O(1)\)
- 특정 인덱스에 항목을 삽입 : \(O(n)\)

링크드 리스트 기본 구조와 용어

노드(Node): 데이터 저장 단위 (데이터값, 포인터)로 구성
포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

장단점

장점	단점
* 데이터 공간을 미리 할당하지 않아도 됨 (배열은 미리 공간을 할당)	* 연결을 위한 별도 데이터 공간이 필요, 저장공간 효율 낮음 * 연결 정보를 찾는 시간 필요, 접근 속도 느림 * 중간 데이터 삭제시, 앞뒤 데이터 연결 재구성하는 작업 필요

Code

Node 클래스 (node.py)

Class Node(object):
  def __init__(self, value=None, pointer=None):
    self.value = value
    self.pointer = pointer

  def getData(self):
    return self.value

  def getNext(self):
    return self.pointer

  def setData(self, newdata):
    self.value = newdata

  def setNext(self, newpointer):
    self.pointer = newpointer

LIFO 연결 리스트

from node import Node

class LinkedListLIFO(object):
  def __init__(self):
    self.head = None
    self.length = 0

  # 헤드부터 각 노드의 값을 출력
  def _printList(self):
    node = self.head
    while node:
      print(node.value, end=" ")
      node = node.pointer
    print()

  # 이전 노드(prev)를 기반으로 노드(node)를 삭제
  def _delete(self, prev, node):
    self.length -= 1
    if not prev:
      self.head = node.pointer
    else:
      prev.pointer = node.pointer

  # 새 노드를 추가. 다음 노드로 헤드 가리키기
  # 헤드는 새 노드를 가리킨다.
  def _add(self, value):
    self.length += 1
    self.head = Node(value, self.head)

  # 인덱스로 노드를 찾는다.
  def _find(self, index):
    prev = None
    node = self.head
    i = 0
    while node and i < index:
      prev = node
      node = node.pointer
      i += 1
    return node, prev, i

  # 값으로 노드를 찾는다.
  def _find_by_value(self, value):
    prev = None
    node = self.head
    found = False
    while node and not found:
      if nod.value == value:
        found = True
      else:
        prev = node
        node = node.pointer
    return node, prev, found

  # 인덱스에 해당하는 노드를 찾아서 삭제
  def deleteNode(self, index):
    node, prev, i = self._find(index)
    if index == i:
      self._delete(prev, node)
    else:
      print("인덱스 {}에 해당하는 노드가 없습니다.".format(index))

  # 값에 해당하는 노드를 찾아서 삭제
  def deleteNodeByValue(self, value):
    node, prev, found = self._find_by_value(value)
    if found:
      self._delete(prev, node)
    else:
      print("값 {}에 해당하는 노드가 없습니다.".format(value))

FIFO 연결 리스트

from node import Node

class LinkedListFIFO(object):
  def __init__(self):
    self.head = None
    self.length = 0
    self.tail = None

  # 헤드부터 각 노드의 값 출력
  def _printList(self):
    node = self.head
    while node:
      print(node.value, end=" ")
      node = node.pointer
    print()

  # 첫 번째 위치에 노드 추가
  def _addFirst(self, value):
    self.length = 1
    node = Node(value)
    self.head = node
    self.tail = node

  # 첫 번째 위치의 노드 삭제
  def _deleteFirst(self):
    self.length = 0
    self.head = None
    self.tail = None
    print("연결 리스트가 비었습니다.")

  # 새 노드를 추가한다. 테일이 있다면 테일의 다음 노드는
  # 새 노드를 가리키고, 테일은 새 노드를 가리킨다.
  def _add(self, value):
    self.length += 1
    node = Node(value)
    if self.tail:
      self.tail.pointer = node
    self.tail = node

  # 새 노드를 추가
  def addNode(self, value):
    if not self.head:
      self._addFirst(value)
    else:
      self._add(value)

  # 인덱스로 노드 찾기
  def _find(self, index):
    prev = None
    node = self.head
    i = 0
    while node and i < index:
      prev = node
      node = node.pointer
      i += 1
    return node, prev, i

  # 값으로 노드 찾기
  def _find_by_value(self, value):
    prev = None
    node = self.head
    found = False
    while node and not found:
      if node.value == value:
        found = True
      else:
        prev = node
        node = node.pointer
    return node, prev, found

  # 인덱스에 해당하는 노드 삭제
  def deleteNode(self, index):
    if not self.head or not self.head.pointer:
      self._deleteFirst()
    else:
      node, prev, i = self._find(index)
      if i == index and node:
        self.length -= 1
        if i == 0 or not prev:
          self.head = node.pointer
          self.tail = node.pointer
        else:
          prev.pointer = node.pointer
      else:
        print("인덱스 {}에 해당하는 노드가 없습니다.".format(index))

  # 값에 해당하는 노드 삭제
  def deleteNodeByValue(self, value):
    if not self.head or not self.head.pointer:
      self._deleteFirst()
    else:
      node, prev, i = self._find_by_value(value)
      if node and node.value == value:
        self.length -= 1
        if i == 0 or not prev:
          self.head = node.pointer
          self.tali = node.pointer
        else:
          prev.pointer = node.pointer
      else:
        print("값 {}에 해당하는 노드가 없습니다.".format(index))

Double 연결 리스트
- 이중 연결 리스트라고도 함
- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

Class Node(object):
  def __init__(self, value=None, pointer=None, prev=None):
    self.value = value
    self.pointer = pointer
    self.prev = prev

  def getData(self):
    return self.value

  def getNext(self):
    return self.pointer

  def getPrev(self):
    return self.prev

  def setData(self, newdata):
    self.value = newdata

  def setNext(self, newpointer):
    self.pointer = newpointer

  def setPrev(self, newprev):
    self.prev = newprev

class DoubleLinkedList(object):
  def __init__(self):
    self.head = None
    self.tail - None
    self.length = 0

  def _printList(self):
    node = self.head
    while node:
      print(node.value, end=" ")
      node = noed.pointer
    print()

  def _addFirst()