링크드 리스트는 data와 next라는 다음 참조 주소를 갖는 속성을 가진 자료 구조이다.

싱글 링크드 리스트

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):
    node = self.head
    while node:
      print (node.data)
      node = node.next
    
  def delete(self, data):
    if self.head == '':
      print ("해당 값을 가진 노드가 없습니다.")
      return
        
    if self.head.data == data:
      temp = self.head
      self.head = self.head.next
      del temp
    else:
      node = self.head
      while node.next:
        if node.next.data == data:
          temp = node.next
          node.next = node.next.next
          del temp
          return
        else:
          node = node.next

• Node라는 클래스를 생성한다. 이는 노드를 생성하기 위한 클래스이다.
• NodeMgmt라는 클래스를 생성한다. 이는 노드를 관리하기 위한 클래스이다.
• add : 리스트에 노드를 추가하는 기능
• desc : 리스트의 노드를 조회하는 기능
• delete : 리스트에서 노드를 삭제하는 기능

더블 링크드 리스트

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

class NodeMgmt:
  def __init__(self, data):
    self.head = Node(data)
    self.tail = self.head
    
  def insert_before(self, data, before_data):
    if self.head == None:
      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.next = node
        return True

  def insert_after(self, data, after_data):
    if self.head == None:
      self.head = Node(data)
      return True            
    else:
      node = self.head
      while node.data != after_data:
        node = node.next
        if node == None:
          return False
        new = Node(data)
        after_new = node.next
        new.next = after_new
        new.prev = node
        node.next = new
        if new.next == None:
          self.tail = new
          return True

  def insert(self, data):
    if self.head == None:
      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):
    node = self.head
    while node:
      print (node.data)
      node = node.next
      
  def search_from_head(self, data):
    if self.head == None:
      return False
    
    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.head == None:
      return False
    
    node = self.tail
    while node:
      if node.data == data:
        return node
      else:
        node = node.prev
        return False

• Node : 노드를 생성하기 위한 클래스 / 데이터와 함께 이전 값 주소와 다음 값 주소를 갖는다.
• NodeMgmt : 노드를 관리하기 위한 클래스
• insert_before : 기존 노드 앞에 새로운 노드 삽입
• insert_after : 기존 노드 뒤에 새로운 노드 삽입
• insert : 빈 리스트에 헤드 노드 삽입
• desc : 리스트에서 노드 조회
• search_from_head : 헤드 쪽에서 부터 검색
• search_from_tail : 꼬리 쪽에서 부터 검색