(자료구조) Linkedlist - 연결 리스트 구조와 종류별 python examples

(자료구조) Linked List - 연결 리스트 구조와 종류 python examples

(배경)

연결 리스트는 1955~1956년에 랜드 연구소에서 앨런 뉴웰, 클리프 셔, 허버트 A. 사이먼이 그들의 정보 처리 언어(IPL)를 위한 1차 자료 구조로서 개발하였다.

(연결 리스트의 종류)

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 순환 연결 리스트, 순환 이중 연결 리스트 등으로 다양합니다.

1. 단일 연결 리스트
2. 이중 연결 리스트
3. 순환 연결 리스트
4. 순환 이중 연결 리스트

(연결 리스트의 구조)

연결 리스트는 배열(ArrayList)과 마찬가지로 Linked List는 선형 데이터 구조입니다. ArrayList와 달리 노드, 주소, 데이터 필드, 링크 필드로 구성됩니다.

[리스트의 구성 요소]
- 노드 : 리스트의 단위
- 주소 : 노드를 가리키는 포인트 주소
- Data 필드 : Data를 저장하는 공간
- 링크 필드: 연결된 이전 또는 다음 노드 주소를 보관하는 포인터 주소 공간

연결 리스트의 구조

▪︎ 연결 리스트의 장점

- (동적 메모리 크기) 데이터 입력 시 노드의 주소가 순차적이지 않아 크기가 동적인 메모리 공간의 어느 곳에 나 둘 수 있음
- (데이터 추가 삭제 용이) 인덱스 대신 현재 위치의 이전과 다음 위치 정보를 이용하여, 각 노드 중간에 삽입, 삭제 시 논리적 주소만 바꿔주면 되기 때문에 데이터 추가, 삭제가 용이함

▪︎연결 리스트의 단점

- 연결된 링크 주소 순서대로 데이터 접근이 가능하므로 접근 속도가 느림

1. 단일 연결 리스트 (단방향 리스트, Singly Linked List)

단일 연결 리스트는 각 노드에 Data를 저장하는 자료 공간(Key)과 노드를 연결하는 한 개의 포인터 주소 공간(Link)으로 구성된다. 리스트의 각 노드의 포인터는 다음 노드를 연결하여 다음 노드로만 이동할 수 있는 것이 단방향 연결 리스트(Singly Linked List)이다.

단일 연결 리스트

#
# 1. single linked list example
#

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

class LinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
       last_node.next = new_node

    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data, end=" ")
            current_node = current_node.next

# Create a new linked list
llist = LinkedList()

# Add nodes to the linked list
llist.add_node(1)
llist.add_node(2)
llist.add_node(3)

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

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

이중 연결 리스트

#
# 2. an example of a doubly linked list in Python
#
class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = new_node
        new_node.prev = current_node

    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data, end=" ")
            current_node = current_node.next
        print()

    def print_reverse_list(self):
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        while current_node is not None:
            print(current_node.data, end=" ")
            current_node = current_node.prev
        print()

#
# Create a new doubly linked list
dllist = DoublyLinkedList()

# Add nodes to the doubly linked list
dllist.add_node(1)
dllist.add_node(2)
dllist.add_node(3)

# Print the doubly linked list
dllist.print_list() # Output: 1 2 3

# Print the doubly linked list in reverse order
dllist.print_reverse_list() # Output: 3 2 1

이 예에서 각 노드에는 속성 prev외에 next 속성이 있습니다. 이렇게 하면 연결된 목록을 양방향으로 탐색할 수 있습니다.

□ 순환 연결 리스트(Circular linked list)

순환 연결 리스트는 모든 노드가 연결되어 원을 형성하는 연결 리스트입니다. 원형 연결 리스트는 첫 번째 노드와 마지막 노드가 서로 연결되어 원을 형성합니다. 노드의 끝에 NULL이 없습니다.

순환 연결 리스트의 장점:

• 모든 노드가 시작점이 될 수 있어서, 어떤 지점에서 시작하 든 지 전체 목록을 탐색할 수 있습니다. 처음 방문한 노드를 다시 방문할 때 순환을 중지하면 됩니다.
• 대기열 구현에 유용하여, 순환 연결 목록을 사용하는 경우 앞뒤에 대한 두 개의 포인터를 유지할 필요가 없습니다. 마지막으로 삽입된 노드에 대한 포인터를 유지할 수 있으며 앞은 항상 마지막의 다음으로 얻을 수 있습니다.

• 순환 목록은 응용 프로그램에서 목록을 반복적으로 이동하는 데 유용합니다. 예를 들어, 여러 응용 프로그램이 PC에서 실행 중인 경우 운영 체제가 실행 중인 응용 프로그램을 목록에 넣은 다음 순환하면서 각 응용 프로그램에 실행할 시간을 준 다음 잠시 기다리게 하는 것이 가능합니다.
• 운영 체제는 순환 목록을 사용하여 목록 끝에 도달하면 목록 맨 앞으로 순환할 수 있도록 하는 것이 편리합니다.
• 순환 이중 연결 목록은 피보나치 힙 과 같은 고급 데이터 구조 구현에 사용됩니다.

순환 연결 리스트의 단점:

• 단일 연결 목록에 비해 순환 목록은 복잡합니다.
• 순환 목록을 뒤집는 것은 순환 목록을 한 번 또는 두 번 뒤집는 것보다 더 복잡합니다.
• 코드가 무한 루프에 빠질 수 있습니다.
• 목록의 끝을 찾고 루프를 제어하는 것이 더 어렵습니다.

3. 순환 단일 연결 리스트 (Circular singly linked list)

순환(원형) 단일 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다. 순환 단일 연결 목록에는 시작이나 끝이 없습니다.

순환 단일 연결 리스트 - Circular singly linked list -

순환 단일 연결 리스트 - Circular singly linked list -

#
# 3. an example of a circular singly linked list in Python:
#

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
            return
        current_node = self.head
        while current_node.next is not self.head:
            current_node = current_node.next
        current_node.next = new_node
        new_node.next = self.head

    def print_list(self):
        current_node = self.head
        while True:
            print(current_node.data, end=" ")
            current_node = current_node.next
            if current_node is self.head:
                break
        print()



# Create a new circular singly linked list
clist = CircularLinkedList()

# Add nodes to the circular singly linked list
clist.add_node(1)
clist.add_node(2)
clist.add_node(3)

# Print the circular singly linked list
clist.print_list() # Output: 1 2 3  (circles back to 1)

이 예제에서 메서드는 마지막 노드의 포인터가 목록의 헤드를 가리키도록 add_node()설정하여 순환 단일 연결 목록에 노드를 추가합니다 .

4. 순환 이중 연결 리스트 (Circularly Doubly Linked List)

순환 이중 연결 리스트는 연속된 두 요소가 이전 포인터와 다음 포인터에 의해 연결되고 마지막 노드가 다음 포인터에 첫 번째 노드를 가리키고 첫 번째 노드는 이전 포인터로 마지막 노드를 가리킵니다.

순환 이중 연결 리스트 -Linked List-

#
# 4. an example of a circular doubly linked list in Python:
#

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

class CircularDoublyLinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = new_node
            new_node.prev = new_node
            return
        last_node = self.head.prev
        last_node.next = new_node
        new_node.prev = last_node
        new_node.next = self.head
        self.head.prev = new_node

    def print_list(self):
        current_node = self.head
        while True:
            print(current_node.data, end=" ")
            current_node = current_node.next
            if current_node is self.head:
                break
        print()

    def print_reverse_list(self):
        current_node = self.head.prev
        while True:
            print(current_node.data, end=" ")
            current_node = current_node.prev
            if current_node is self.head.prev:
                break
        print()

#
# Create a new circular doubly linked list
cdllist = CircularDoublyLinkedList()

# Add nodes to the circular doubly linked list
cdllist.add_node(1)
cdllist.add_node(2)
cdllist.add_node(3)

# Print the circular doubly linked list
cdllist.print_list() # Output: 1 2 3 (circles back to 1)

# Print the circular doubly linked list in reverse order
cdllist.print_reverse_list() # Output: 3 2 1 (circles back to 3)

이 예제에서 각 노드에는 prev및 next포인터가 모두 있으므로 연결된 목록을 양방향으로 순회할 수 있습니다. 이 메서드는 새 노드와 마지막 노드의 및 포인터를 적절하게 add_node()설정하여 순환 이중 연결 목록에 노드를 추가합니다 .

[참고자료]


https://www.javatpoint.com/ds-types-of-linked-list

https://www.geeksforgeeks.org/circular-linked-list/
https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-circular-doubly-linked-list/