4. 링크드 리스트(Linked List)

링크드 리스트(Linked List)

링크드리스트 구조

• 연결 리스트라고도 함
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
• 파이썬은 리스트 타입이 링크드리스트 기능을 모두 지원

 

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

예

• Node 구현

• 보통 파이썬에서 링크드 리스트 구현 시, 파이썬 클래스를 사용함

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

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

 

• Node와 Node 연결

  node1 = Node(1)
  node2 = Node(2)
  node1.next = node2
  head = node1

 

• 링크드 리스트로 데이터 추가하기

class Node :
  def__init__(self, data, next=None) :
    self.data = data
    self.next = next
  
  def add(data) :
    node = head
    while node.next :
      node = node.next
    node.next = Node(data)

node1 = Node(1)
head = node1
for index in range(2,10) :
  add(index)

 

• 링크드 리스트 데이터 출력하기(검색)

node = head
while node.next :
  print(node.data)
  node = node.next
print(node.data)

 

링크드 리스트의 장단점(C)

• 장점
  • 미리 데이터 공간을 할당하지 않아도 됨
• 단점
  • 연결을 위한 별도 데이터 공간이 필요, 저장 공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

링크드 리스트 구현

class Node :
  def __init__(self, data, next=None) :
    self.data = data
    self.next = next
    
class LinkedList :
  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) :  # 링크드 리스트 내 해당 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
          
  def search(data):         # 링크드 리스트 내 데이터 검색
    node = self.head
    while node :
      if node.data == data :
        return node
      else :
        node = node.next

 

더블 링크드 리스트 구현

• 이중 연결 리스트
• 장점 : 양방향으로 연결되어 노드 탐색이 양쪽으로 가능

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

class doubleLinkedList :
  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