포인터 기반의 연결 방식(3) - 추상 데이터 타입(연결리스트)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 자료구조 내용입니다

 

목차

• 추상 데이터 타입 - 연결리스트
• 연결리스트의 종류
• (단일, 이중, 원형)구현

 

<추상 데이터 타입 - 연결리스트, 해시테이블>

연결 리스트(Linked list)

• 데이터를 노드의 형태로 저장.
• 노드에 데이터와 다음 노드를 가르키는 포인터를 담은 구조로 이루어진 선형 리스트
• 연결 리스트로 스택(LIFO)과 큐(FIFO) 구현 가능
• 장점 : 연결리스트의 길이를 동적으로 조절가능, 데이터의 삽입과 삭제가 쉬움.
• 단점 : 임의의 노드에 바로 접근할 수 없고, 첫 노드부터 탐색해야함. 다음 노드의 위치를 저장하기 위한 추가 공간이 필요함. - 시간복잡도O(n)

 

연결 리스트의 종류 - 연결되는 방향에 따라 구분

단일 연결 리스트 : 각 노드에 데이터 공간과 한 개의 포인터 공간(다음 노드)이 존재.

이중 연결 리스트 : 각 노드에 데이터 공간과 두 개의 포인터 공간(이전 노드, 다음 노드)이 존재.

원형 연결 리스트 : 머리와 꼬리가 연결되어 순환 구조를 가짐. 포인터의 개수(1개 일수도 있고 2개 일수도)에 상관없이 노드의 Next가 none인 경우가 없이 끊임 없이 이어짐.

 

단일 연결 리스트 구현

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: # empty가 아닌 경우
            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):  # p가 가리키는 노드의 앞 노드 삭제
        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 DList:
    class Node:
        def __init__(self, item, prev, link):  # 노드 생성자
            self.item = item  # 항목
            self.prev = prev  # 뒤 노드 레퍼런스
            self.next = link  # 앞 노드 레퍼런스

    def __init__(self):  # 이중 연결 리스트 생성자
        # 두 더미 노드(dummy node)를 생성하는데 항목을 저장하지는 않음
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0

    def size(self):
        return self.size

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

    def insert_before(self, p, item):  # 새 노드를 노드 p 앞에 삽입
        t = p.prev
        n = self.Node(item, t, p)  # 생성한 노드를 n이 참조
        p.prev = n  # 뒤 노드와 새 노드 연결
        t.next = n  # 앞 노드와 새 노드 연결
        self.size += 1

    def insert_after(self, p, item):  # 새 노드를 노드 p 뒤에 삽입
        t = p.next
        n = self.Node(item, p, t)  # 생성한 노드를 n이 참조
        t.prev = n  # 앞 노드와 새 노드 연결
        p.next = n  # 뒤 노드와 새 노드 연결
        self.size += 1

    def delete(self, x):  # 노드 x 삭제
        # x가 참조하는 노드는 연결 리스트에서 분리되어 가비지 컬렉션에 의해 처리됨
        f = x.prev
        r = x.next
        f.next = r  # x를 건너뛰고 x의 앞뒤 노드를 연결
        r.prev = f  # x를 건너뛰고 x의 앞뒤 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.isempty():
            print('List is empty.')
        else:
            p = self.head.next
            while p != self.tail:
                if p.next != self.tail:
                    print(p.item, ' <=> ', end='')
                else:
                    print(p.item)
                p = p.next  # 노드를 차례로 방문

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

[참고 사이트]

 

원형 연결 리스트 구현

class CList:
    class Node:
        def __init__(self, item, link):  # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스

    def __init__(self):  # 원형 연결 리스트 생성자
        self.last = None
        self.size = 0

    def no_items(self):
        return self.size

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

    def insert(self, item):  # 새 항목을 연결 리스트의 첫 노드로 삽입
        n = self.Node(item, None)  # 새 항목을 저장할 노드를 생성하여 n이 참조
        if self.is_empty():  # 연결 리스트가 empty인 경우
            n.next = n  # 새 노드는 자신을 참조
            self.last = n  # last는 새 노드를 참조
        else:
            n.next = self.last.next  # 새 노드는 첫 노드를 참조
            self.last.next = n  # last가 참조화는 노드와 새 노드 연결
        self.size += 1

    def first(self):
        if self.is_empty():
            raise EmptyError('Underflow')
        f = self.last.next
        return f.item

    def delete(self):  # 연결 리스트의 첫 노드를 삭제
        if self.is_empty():
            raise EmptyError('Underflow')
        x = self.last.next
        if self.size == 1:  # 연결 리스트에 노드가 1개인 경우
            self.last = None  # empty 리스트가 됨
        else:  # 노드가 2개 이상인 경우
            self.last.next = x.next  # last가 참조하는 노드가 두번째 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.is_empty():
            print('List is empty.')
        else:
            f = self.last.next
            p = f
            while p.next != f:  # 첫 노드를 다시 방문하면 중단
                print(p.item, ' -> ', end='')
                p = p.next  # 노드를 차례로 방문
            print(p.item)

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