알고리즘 - 연결 리스트

연결리스트

연결리스트, Linked List 는 각 노드들이 한 줄로 연결되어 있는 방식으로 각 노드는 데이터와 포인터 (다음 노드의 정보)를 가지고 있다. 연결리스트는 일반적인 배열과 다르게 삽입과 삭제가 O(1)에 가능하다는 장점이 있다. 하지만 특정 n번 째 정보를 찾는 데에는 O(n)시간이 걸린다는 단점도 있다.

이중 연결리스트는 이 포인터에 앞, 뒤 정보가 모두 담겨 있다.

마지막 노드의 포인터가 첫 번째 노드를 가르킨다.

구현

먼저 가장 최초에 있는 노드를 header라고 부르고, 맨 마지막에 있는 노드를 tail이라고 부른다. 또한 일반적인 배열과는 다르게, 배열의 시작을 1로 하고, 0번째 노드는 비어있는 노드로 가정한다. 이는 구현에 있어 조금 더 편하게 하기 위함이다.

그리고 구현해볼 메소드는 다음과 같다.

• print: 리스트를 볼 수 있도록 프린트 한다.
• getAt(n): n번째 노드를 꺼낸다.
• insertAt(n, node): n번째에 node를 삽입한다.
• insertAfter(prev, new): prev이후에 new를 삽입한다.
• popAt(n): n번째 노드를 삭제한다.
• popAfter(prev): prev 이후 노드를 삭제한다.
• size: 전체 노드 개수를 계산한다.
• traverse: 전체 노드를 배열로 리턴한다.

python

Node

class Node:
  def __init__(self, item):
    self.data = item # 데이터 정보
    self.next = None # 다음 노드 정보

Linked List

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

  def traverse(self):
    result = []
    curr = self.head
    while curr.next:
      curr = curr.next
      result.append(curr.data)
    return result

  def getAt(self, n):
    if n < 0 or n > self.size:
      return None

    i = 0
    curr = self.head
    while i < n:
      curr = curr.next
      i += 1

    return curr

  def insertAfter(self, prev, new):
    # 새로운 노드의 다음 노드는 이전 노드의 다음 정보
    new.next = prev.next
    # prev가 tail일 경우
    if prev.next is None:
      self.tail = new
    # 이제 이전 노드의 다음 노드는 사로운 노드
    prev.next = new
    self.size += 1


  def insertAt(self, n, new):
    if n < 1 or n > self.size + 1:
      return False

    # tail에 들어갈 경우
    if n != 1 and n == self.size + 1:
      prev = self.tail
    else:
      prev = self.getAt(n - 1)

    return self.insertAfter(prev, new)

  def popAfter(self, prev):
    popData = prev.next.data
    ## tail 을 제거하려고 할때
    if prev.next.next is None:
      self.tail = prev
      prev.next = None
    else:
      prev.next = prev.next.next

    self.size -= 1

    return popData

  def popAt(self, n):
    if n < 1 or n > self.size:
      raise IndexError

    # head일 경우
    if n == 1:
      prev = self.head
    else:
      prev = self.getAt(n - 1)

    return self.popAfter(prev)

  def print(self):
    if self.size == 1:
      print("this linked list is empty")
    else:
      print(self.traverse())