[자료구조] 단순/원형/이중 연결리스트(Linked List) 구현 - 파이썬(Python)

연결리스트(Linked List)

• 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 선형 자료구조
• 연결리스트는 Node로 구성되어 있고, Node 안에는 Data와 Link(Next)로 구성
  • Data: 데이터 값 저장
  • Link(Next): 다음 노드를 가리킴

장점

• 데이터 추가, 삭제에 유리
  • 배열: 시간복잡도 O(n)
  • 연결리스트: 시간복잡도 O(1)
• 공간복잡도 측면에서 유리 (배열처럼 연속된 공간을 할당하지 않고 필요 시에만 메모리를 동적 할당하기 때문)
  • 메모리 누수 X
  • 유연한 메모리 관리

단점

• 데이터 탐색 시 불리 (데이터의 논리적 저장 순서와 물리적 저장 순서가 일치하지 않아 인덱스 접근이 아닌 전체를 순회해야 하기 때문)
  • 배열: 시간복잡도 O(1)
  • 연결리스트: 시간복잡도 O(n)
• 테이터 정렬 시 불리

 

 

단순 연결리스트(Singly Linked List)

• 가장 단순히 다음 노드에 대한 참조만 고려한 형태의 연결리스트
• 마지막 노드는 항상 NULL을 가리킴
• 헤드 포인터의 주소나 다음 노드의 주소가 부정확할 때 데이터 유실의 위험이 높음 (안정적X)

 

1. 노드 생성

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

 

2. 연결리스트 초기화

class SimplyLinkedList:
    def __init__(self):
        self.nodeCount = 0  # 연결리스트 내 노드 수
        self.head = None  # 첫 번째 노드
        self.tail = None  # 마지막 노드

 

3. 노드 삽입

# 맨 앞(head)에 노드 삽입
def insert_front(self, val):
    new_node = Node(val)
    
    if self.head is None:  # 빈 연결리스트일 때
    	self.head = new_node
        self.tail = new_node
        
    else:  # 빈 연결리스트가 아닐 때
    	new_node.next = self.head
        self.head = new_node
    
    self.nodeCount += 1
 
 
# 중간에 노드 삽입
def insert_middle(self, target, val):
    current = self.head
    
    while current != None:
    	previous = current
        current = current.next
        
        if previous.data == target:  # target 값을 가진 노드 뒤에 삽입
        	new_node = Node(val)
            new_node.next = current
            previous.next = new_node
            self.nodeCount += 1
            break
                    	

# 맨 끝(tail)에 노드 삽입
def insert_back(self, val):
    new_node = Node(val)
    
    if self.head is None:  # 빈 연결리스트일 때
    	self.head = new_node
        self.head = new_node
        
    else:  # 빈 연결리스트가 아닐 때
    	self.tail.next = new_node
        self.tail = new_node
        
    self.nodeCount += 1

 

4. 노드 삭제

def delete_front(self):
    # 연결리스트가 비어있지 않을 경우
    current = self.head
    self.head = self.head.next
    del(current)
    self.nodeCount -= 1
 
 
def delete_middle(self, target):
    current = self.head
    
    while current != None:
    	previous = current
        currrent = current.next
        
        if curren.data == target:
            previous.next = current.next
            del(current)
            self.nodeCount -= 1
            break
            
            
def delete_back(self):
    # 연결리스트가 비어있지 않을 경우
    previous = None
    current = self.head
    
    while current.next != None:  # tail 노드를 가리키고있는 바로 이전 노드를 찾아야하므로 전체 순회
    	previous = current
        currrent = current.next
    
    previous.next = None
    self.tail = previous
    del(current)
    self.nodeCount -= 1

 

 

원형 연결리스트(Circular Linked List)

• 단순 연결리스트에서 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정한 형태의 연결리스트
• NULL을 가리키는 노드가 없음

 

※ 원형 연결리스트의 구현 방식은 단순 연결리스트와 그 원리가 비슷하기 때문에 원형 연결리스트의 구현은 생략하겠음.

 

 

이중 연결리스트(Doubly Linked List)

• 단순 연결리스트에서 다음 노드 뿐만 아니라 이전 노드에 대한 참조도 고려한 형태의 연결리스트
• 노드와 노드가 상호 연결
• 역순 접근 및 탐색 가능

 

1. 노드 생성

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

 

2. 연결리스트 초기화

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 첫 번째 노드
        self.tail = None  # 마지막 노드
        self.head.next = self.tail
        self.tail.prev = self.head

 

3. 노드 삽입

# 맨 앞(head)에 노드 삽입
def insert_front(self, val):
    new_node = Node(val)
    
    if self.head is None:  # 빈 연결리스트일 때
    	self.head = new_node
        self.tail = new_node
        self.head.next = tail
        self.tail.prev = head
        
    else:  # 빈 연결리스트가 아닐 때
    	new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    
    self.nodeCount += 1
 
 
# 중간에 노드 삽입
def insert_middle(self, target, val):
    current = self.head
    
    while current != None:
    	previous = current
        current = current.next
        
        if previous.data == target:  # target 값을 가진 노드 뒤에 삽입
        	new_node = Node(val)
            new_node.next = current
            current.prev = new_node
            previous.next = new_node
            new_node.prev = previous
            self.nodeCount += 1
            break
                    	

# 맨 끝(tail)에 노드 삽입
def insert_back(self, val):
    new_node = Node(val)
    
    if self.head is None:  # 빈 연결리스트일 때
    	self.head = new_node
        self.head = new_node
        self.head.next = tail
        self.tail.prev = head
        
    else:  # 빈 연결리스트가 아닐 때
    	self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node
        
    self.nodeCount += 1

 

4. 노드 삭제

def delete_front(self):
    # 연결리스트가 비어있지 않을 경우
    current = self.head
    self.head = self.head.next
    self.head.prev = None
    del(current)
    self.nodeCount -= 1
 
 
def delete_middle(self, target):
    current = self.head
    
    # target은 압쪽에 위치한다고 가정 (target 데이터가 tail과 가깝게(뒷쪽에) 위치한다면 역순회로 구현)
    while current != None:
        currrent = current.next
        
        if curren.data == target:
        	left = current.prev
            right = current.next
            left.next = right
            right.prev = left
            del(current)
            self.nodeCount -= 1
            break
            
            
def delete_back(self):
    # 연결리스트가 비어있지 않을 경우
    current = self.tail
    self.tail = self.tail.prev
    self.tail.next = None
    del(current)
    self.nodeCount -= 1