단순연결리스트(Singly Linked List) 이론과 파이썬 구현

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

단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 노드들을 한 방향으로 연결하여 리스트를 구현한 자료구조입니다.

 

단순연결리스트는 삽입이나 삭제 시 항목들의 이동이 필요없습니다.

하지만 항목을 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색을 이용해야 합니다.

 

 

단순연결리스트의 기본 구조

 

단순연결리스트의 기본 구조입니다.

head는 단순연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스를 가집니다. 

item은 항목으로 node값이 저장됩니다.

reference는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

 

Insert_front() : 새 노드를 단순연결리스트의 맨 앞에 삽입, 시간복잡도 : O(1)

Insert_after() : p가 가리키는 노드의 다음에 삽입, 시간복잡도 : O(1)

 

delete_front() : 단순연결리스트의 첫 노드 삭제, 시간복잡도 : O(1)

delete_after() : p가 가리키는 노드의 다음 노드 삭제, 시간복잡도 : O(1)

 

 

단순연결리스트의 파이썬 코드입니다.

class SList:
    
    class Node:
        def __init__(self, item, link):  # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스
            
    def __init__(self):  # 단순 연결 리스트 생성자
        self.head = None
        self.size = 0  

    def size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_front(self, item):  # 연결 리스트의 맨 앞에 새 노드 삽입
        if self.is_empty():  # 연결 리스트가 empty인 경우
            self.head = self.Node(item, None)  # head가 새 노드 참조
        else: 
            self.head = self.Node(item, self.head)  # head가 새 노드 참조
        self.size += 1

    def insert_after(self, item, p):  # p가 가리키는 노드 다음에 새 노드 삽입
        p.next = SList.Node(item, p.next)  # 새 노드가 p 다음 노드
        self.size += 1

    def delete_front(self):  # 연결 리스트의 맨 앞 노드 삭제 
        if self.is_empty():  # empty인 경우 에러 처리
            raise EmptyError('Underflow')
        else:
            self.head = self.head.next  # head가 둘째 노드를 참조
            self.size -= 1

    def delete_after(self, p):  # p가 가리키는 노드의 다음 노드 삭제
        if self.is_empty():  # empty인 경우 에러 처리
            raise EmptyError('Underflow')
        t = p.next
        p.next = t.next  # p 다음 노드를 건너뛰어 연결
        self.size -= 1

    def search(self, target):  # 노드 탐색(순차탐색)
        p = self.head
        for k in range(self.size): 
            if target == p.item:
                return k  # 탐색 성공
            p = p.next
        return None  # 탐색 실패

    def print_list(self):
        p = self.head
        while p:
            if p.next != None:
                print(p.item, ' -> ', end='')
            else:
                print(p.item)
            p = p.next  # 노드들을 순차탐색

class EmptyError(Exception):  # 에러 처리
    pass



s = SList() #객체생성
s.insert_front('orange')
s.insert_front('apple')
s.insert_after('cherry',s.head.next)
s.insert_front('pear')
s.print_list()

print('cherry는 %d번째' % s.search('cherry'))
print('kiwi는', s.search('kiwi'))   

print('배 다음 노드 삭제 후:\t\t', end='')
s.delete_after(s.head)
s.print_list()

print('첫 노드 삭제 후:\t\t', end='')
s.delete_front()
s.print_list()
print('첫 노드로 망고, 딸기 삽입 후:\t', end='')
s.insert_front('mango')
s.insert_front('strawberry')
s.print_list()
s.delete_after(s.head.next.next)

print('오렌지 다음 노드 삭제 후:\t', end='')
s.print_list()

 

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.