[자료구조] : 연결리스트(Linked List, Double Linked List)

# Linked List

#개념은 아래 링크에서 직접 값을 넣고 빼보면서 확인해볼 것.

www.cs.usfca.edu/~galles/visualization/StackLL.html

Linked List Stack Visualization

class Node:
  def __init__(self, data, next=None):
    self.data = data
    self.next = next
 
class NodeMgmt:
  def __init__(self, data):
    self.head = Node(data)
 
  def add(self, data):
    if self.head == '':
      self.head = Node(data)
    else:
      node = self.head
      while node.next:
        node = node.next
      node.next = Node(data)
 
  def desc(self):
    if self.head == '':
      return
    else:
      node = self.head
      while node:
        print(node.data)
        node = node.next
 
  def delete(self, data):
    # 1. 삭제할 노드가 헤더 노드인경우
    if self.head.data == data:
      tmp = self.head
      self.head = self.head.next
      del tmp
    # 2. 삭제할 노드가 중간이거나 맨마지막인경우
    else:
      node = self.head
      while node.next:
        if node.next.data == data:
          tmp = node.next
          node.next = node.next.next
          del tmp
          return
        else:
          node = node.next
    
 
 
node = NodeMgmt(1)
node.add(2)
node.add(3)
node.add(4)
node.add(5)
node.desc()
node.delete(5)
print('============')
node.desc()

 

#Double Linked List

#개념은 아래 링크에서 직접 값을 넣고 빼보면서 확인해볼 것.

www.cpp.edu/~ftang/courses/CS240/lectures/dlist.htmlwww.geeksforgeeks.org/doubly-linked-list-tutorial/

CS240: Data Structures & Algorithms I

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

class Node:   def __init__(self, data, prev=None, next=None):     self.data = data     self.prev = prev     self.next = next   class NodeMgmt:   def __init__(self, data):     self.head = Node(data)     self.tail = self.head      def insert(self, data):     if self.head == '':       self.head = Node(data)     else:       node = self.head       while node.next:         node = node.next       new = Node(data)       node.next = new       new.prev = node       self.tail = new      def desc(self):     if self.head == '':       return     else:       node = self.head       while node:         print(node.data)         node = node.next      def search_from_head(self, data):     if self.head == '':       return False     else:             node = self.head       while node:         if node.data == data:           return node         else:           node = node.next       return False     def search_from_tail(self, data):     if self.tail == '':       return False     else:       node = self.tail       while node:         if node.data == data:           return node         else:           node = node.prev       return False       def insert_before(self, data, before_data):     if self.head == '':       self.head = Node(data)       return True     else:       node = self.tail       while node.data != before_data:         node = node.prev         if node == None:           return False              new = Node(data)       before_new = node.prev       before_new.next = new       new.prev = before_new       new.next = node       node.prev = new       return True             node = NodeMgmt(1) node.insert(2) node.insert(3) node.insert(4) node.desc() if node.search_from_tail(5):   print(node.search_from_tail(5).data) else:   print("데이터가 존재하지 않습니다.")   if node.search_from_head(3):   print(node.search_from_head(3).data) else:   print("데이터가 존재하지 않습니다.") node.insert_before(10, 3) node.desc()                    Colored by Color Scripter

cs