자료구조(파이썬) - 연결 리스트 (Linked List)

교육 정보

• 교육 명: 경기미래기술학교 AI 교육
• 교육 기간: 2023.05.08 ~ 2023.10.31
• 오늘의 커리큘럼:
  파이썬 자료구조
  (7/31 ~ 8/18)
• 강사: 이현주, 이애리 강사님
• 강의 계획:
  1. 자료구조

자료구조

연결 리스트/링크드 리스트 (Linked List)

• 하나의 노드에 데이터/다음에 연결될 데이터에 대한 정보를 가지고있는 자료구조
  ex) linked1 - linked2 - linked3이 순서대로 연결되어있고 각 1, 2, 3이라는 데이터를 가지고있다고 하면 각 노드는

linked1.data = 1
linked1.next = linked2

linked2.data = 2
linked2.next = linked3

linked3.data = 3
linked3.next = None

와 같은 정보를 가짐
→ 메모리상에서는 연속적이지 않음 (정보로만 연결)

• 노드 클래스 / 링크드 리스트 클래스 / 연산

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

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

  def __str__(self):
    if self.head is None:
      return '|empty linked list|'
    res_str = '|'
    iterator = self.head
    while iterator is not None:
      res_str += f'{iterator.data}|'
      iterator = iterator.next
    return res_str

  # 노드 추가 
  def append(self, data):
    new_node = Node(data)
    if self.head is None:
      self.head = new_node
      self.tail = new_node
    else:
      self.tail.next = new_node
      self.tail = new_node
    # 시간 복잡도 O(1)

  # 인덱스로 노드에 접근
  def find_node_at(self, idx):
    iterator = self.head
    for _ in range(idx):
      iterator = iterator.next
    return iterator
    # 시간 복잡도 O(n)

  # 데이터 값을 가지는 노트를 탐색
  def find_node_by_data(self, data):
    iterator = self.head
    while iterator is not None:
      if iterator.data == data:
        return iterator
      else:
        iterator = iterator.next
    return None
    # 시간 복잡도 O(n)

  # 이전 노드와 데이터를 받아 새로운 노드를 삽입 (index만 받아서 함수내에서 이전 노드 계산하는 방식도 가능)
  def insert_after(self, previous_node, data):
    new_node = Node(data)
    if previous_node == self.tail:
      self.tail.next = new_node
      self.tail = new_node
    else:
      new_node.next = previous_node.next
      previous_node.next = new_node
    # 시간 복잡도 O(1)이지만 실제로는 previous_node를 받아와야 하므로 O(n)

  # 링크드리스트의 맨 앞에 노드 추가 (prepend)
  def prepend(self, data):
    new_node = Node(data)
    if self.head is None:
      self.head = new_node
      self.tail = new_node
    else:
      new_node.next = self.head
      self.head = new_node
    # 시간 복잡도 O(1)

  def delete_after(self, previous_node):
    data = previous_node.next.data
    if previous_node is self.tail:
      previous_node.next = None
      self.tail = previous_node 
    else:
      previous_node.next = previous_node.next.next
    return data 
    # 시간 복잡도 O(1)이지만 실제로는 previous_node를 받아와야 하므로 O(n)

  def pop_left(self):
    popped = self.head.data
    # 링크드 리스트가 비어있는 경우는 없다고 가정
    if self.head is self.tail:  # '==' 말고 객체 자체가 같음을 확인하는 'is'를 사용하는게 좋음!!
      self.head = None
      self.tail = None
    else:
      self.head = self.head.next
    return popped
    # 시간 복잡도 O(1)

#
#결과

my_list = LinkedList()

my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.append(4)
my_list.append(5)

print('# print with iterator')
iterator = my_list.head

while iterator is not None:
  print(iterator.data)
  iterator = iterator.next

# __str__
print('\n# __str__')
print(my_list)


# find_node_at
print('\n# find_node_at')
print(my_list.find_node_at(3).data)
print(my_list.find_node_at(1).data)
my_list.find_node_at(1).data = 22
print(my_list.find_node_at(1).data)

# find_node_by_data
print('\n# find_node_by_data')
print(my_list.find_node_by_data(4))
print(my_list.find_node_by_data(23))

# insert after
print('\n# insert after')
print(my_list)
node_at_2 = my_list.find_node_at(2)
my_list.insert_after(node_at_2, 7)
print(my_list)

my_list.insert_after(my_list.tail, 27)
print(my_list)

#prepend
print('\n# prepend')
print(my_list)
my_list.prepend(0)
print(my_list)
print('# prepend to empty linked list')
new_list = LinkedList()
new_list.prepend(123)
print(new_list)
new_list.prepend(456)
print(new_list)

# delete
print('\n# delete after')
print(my_list)
node_at_2 = my_list.find_node_at(2)
my_list.delete_after(node_at_2)
print(my_list)
print('# delete after - tail (with print)')
print(my_list)
node_2from_back = my_list.find_node_at(5)
print(my_list.delete_after(node_2from_back), '→ 지워진 값 return')
print(my_list)

더미 노드

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

class LinkedList:
  def __init__(self):
    self.head = Node("dummy")
    self.tail = None

  # 인덱스로 노드에 접근
  def find_node_at(self, idx):
    iterator = self.head.next # head가 더미노드라서 반영해줌
    for _ in range(idx):
      iterator = iterator.next
    return iterator

  # 이전 노드와 데이터를 받아 새로운 노드를 삽입 
  def insert_after(self, previous_node, data):
    new_node = Node(data)
    new_node.next = previous_node.next
    previous_node.next = new_node
    # dummy head가 있으므로 prev가 없을 경우를 따로 상정할 필요가 없음 

• 더미 헤드 노드를 사용할 경우 첫번째 자리에 노드를 삽입하거나 삭제할때 예외를 둘 필요가 없지만 인덱스로 노드 정보를 받아올때 더미를 염두에 두고 받아와야 해서 전반적으로 봤을때 이점은 생각해봐야 할 듯

이중 연결 리스트/더블리 링크드 리스트 (Doubly Linked List)

• 하나의 노드에 데이터/이전데이터/다음에 연결될 데이터에 대한 정보를 가지고있는 자료구조

class Node:
  '''doubly linked list node'''
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

class LinkedList:
  '''doubly linked list'''
# ==============================================
  def __init__(self):
    self.head = None
    self.tail = None

  def __str__(self):
    if self.head is None:
      return '|empty linked list|'
    res_str = '|'
    iterator = self.head
    while iterator is not None:
      res_str += f'{iterator.data}|'
      iterator = iterator.next
    return res_str

  # 인덱스로 노드에 접근
  def find_node_at(self, idx):
    iterator = self.head
    for _ in range(idx):
      iterator = iterator.next
    return iterator
    # 시간 복잡도 O(n)

  # 데이터 값을 가지는 노트를 탐색
  def find_node_by_data(self, data):
    iterator = self.head
    while iterator is not None:
      if iterator.data == data:
        return iterator
      else:
        iterator = iterator.next
    return None
    # 시간 복잡도 O(n)
# ===위 4개 method는 싱글리 링크드 리스트와 완전히 같음===

  # 노드 추가
  def append(self, data):
    new_node = Node(data)
    if self.head is None:
      self.head = new_node
      self.tail = new_node
    else:
      self.tail.next = new_node
      new_node.prev = self.tail # 바뀐 부분
      self.tail = new_node

  # 이전 노드와 데이터를 받아 새로운 노드를 삽입
  def insert_after(self, previous_node, data):
    new_node = Node(data)
    if previous_node == self.tail:
      self.tail.next = new_node
      new_node.prev = self.tail # 바뀐 부분
      self.tail = new_node
    else:
      new_node.prev = previous_node
      new_node.next = previous_node.next
      previous_node.next = new_node
      previous_node.next.prev = new_node
      # 바뀐 부분


  # 링크드리스트의 맨 앞에 노드 추가 (prepend)
  def prepend(self, data):
    new_node = Node(data)
    if self.head is None:
      self.head = new_node
      self.tail = new_node
    else:
      new_node.next = self.head
      self.head.prev = new_node # 바뀐 부분
      self.head = new_node
    # 시간 복잡도 O(1)

  def delete_after(self, node_to_delete):
    # node_to_delete가 마지막 노드인경우
    if node_to_delete is self.head and node_to_delete is self.tail:
      self.head = None
      self.tail = None
    # node_to_delete가 head이지만 마지막 노드는 아닌 경우
    elif self.head is node_to_delete:
      self.head = self.head.next
      self.head.prev = None
    # node_to_delete가 tail인 마지막 노드는 아닌 경우
    elif self.tail is node_to_delete:
      self.tail = self.tail.prev
      self.tail.next = None
    # node_to_delete가 두 노드 사이에 있는 경우
    else:
      node_to_delete.prev.next = node_to_delete.next
      node_to_delete.next.prev = node_to_delete.prev
    return node_to_delete.data
    # 사실상 시간 복잡도가 O(n)인 싱글리 링크드 리스트와 다르게 시간 복잡도가 항상 O(1)
    # 다른 시간 복잡도는 그대로지만 맨 뒤 노드를 지우는 경우는 더블리 링크드 리스트가 효율적

  def pop_left(self):
    popped = self.head.data
    # 링크드 리스트가 비어있는 경우는 없다고 가정
    if self.head is self.tail:  # '==' 말고 객체 자체가 같음을 확인하는 'is'를 사용하는게 좋음!!
      self.head = None
      self.tail = None
    else:
      self.head = self.head.next
    return popped
    # 시간 복잡도 O(1)


my_list = LinkedList()

my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.append(4)
my_list.append(5)

print('# print with iterator')
iterator = my_list.head

while iterator is not None:
  print(iterator.data)
  iterator = iterator.next

# __str__
print('\n# __str__')
print(my_list)


# find_node_at
print('\n# find_node_at')
print(my_list.find_node_at(3).data)
print(my_list.find_node_at(1).data)
my_list.find_node_at(1).data = 22
print(my_list.find_node_at(1).data)

# find_node_by_data
print('\n# find_node_by_data')
print(my_list.find_node_by_data(4))
print(my_list.find_node_by_data(23))

# insert after
print('\n# insert after')
print(my_list)
node_at_2 = my_list.find_node_at(2)
my_list.insert_after(node_at_2, 7)
print(my_list)

my_list.insert_after(my_list.tail, 27)
print(my_list)

#prepend
print('\n# prepend')
print(my_list)
my_list.prepend(0)
print(my_list)
print('# prepend to empty linked list')
new_list = LinkedList()
new_list.prepend(123)
print(new_list)
new_list.prepend(456)
print(new_list)

# delete
print('\n# delete after')
print(my_list)
node_at_2 = my_list.find_node_at(2)
my_list.delete_after(node_at_2)
print(my_list)
print('# delete after - tail (with print)')
print(my_list)
node_2from_back = my_list.find_node_at(5)
print(my_list.delete_after(node_2from_back), '→ 지워진 값 return')
print(my_list)

#
# 결과

# print with iterator
1
2
3
4
5

# __str__
|1|2|3|4|5|

# find_node_at
4
2
22

# find_node_by_data
<__main__.Node object at 0x794a607bb610>
None

# insert after
|1|22|3|4|5|
|1|22|3|7|4|5|
|1|22|3|7|4|5|27|

# prepend
|1|22|3|7|4|5|27|
|0|1|22|3|7|4|5|27|
# prepend to empty linked list
|123|
|456|123|

# delete after
|0|1|22|3|7|4|5|27|
|0|1|3|7|4|5|27|
# delete after - tail (with print)
|0|1|3|7|4|5|27|
5 → 지워진 값 return
|0|1|3|7|4|27|