[Python, C] Linked List

1️⃣ Linked List (연결 리스트) 개요

💡 Linked List : 노드들이 링크에 의해 순차적으로 연결된 자료구조, 노드는 값을 저장하는 공간과 노드를 연결하는 링크로 구성됨.

C언어의 정적 배열은 선언 시점에 크기를 지정해야 하고 이후 수정이 불가능하지만, 연결 리스트는 필요할 때마다 노드를 생성하여 추가할 수 있으며 최대 노드의 수를 미리 설정할 필요가 없다.
사용할 공간의 규모를 미리 알고 있는 경우는 정적 배열을 사용해도 문제가 없지만 그렇지 않다면 연결 리스트를 사용하는 것이 좋다.

 

👉  연결 리스트의 종류

▫️   단일 연결 리스트 ( Singly linked list ) : 노드들이 한 방향으로만 연결된 구조

▫️   이중 연결 리스트 ( Doubly linked list ) : 노드들이 앞, 뒤 양방향으로 연결된 구조

 

▫️   체인 ( chain ) : 연결 리스트가 마지막 노드에서 끝나는 구조

▫️   순환 연결 리스트 ( circular linked list ) : 연결 리스트에서 마지막 노드가 다시 첫 노드와 연결되는 구조

 

2️⃣ 구현 코드

1. 단일 연결 리스트

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def isEmpty(self):
        return not self.head
    
    def view(self):  
        temp = self.head
        print("[", end=' ')
        while temp:  # [] 안에 리스트의 첫 노드부터 순서대로 모든 노드 값 출력
            print(temp.data, end = ' ')
            temp = temp.link
        print("]", end= ' ')
        if self.head:
            print("H=", self.head.data, "T=", self.tail.data)
        else:
            print("빈 리스트")

    def attach(self, item):   # 노드를 연결 리스트 뒤에 추가하는 연산
        node = Node(item)
        if not self.head:
            self.head = node
            self.tail = node
        elif self.tail: 
            self.tail.link = node
            self.tail = node

lst1 = SinglyLinkedList()
for item in [100, 200, 300]:
    lst1.attach(item)
    lst1.view()

 -  output

 

 

 

이 글의 설명 및 코드는 책( 파이썬으로 배우는 자료구조 프로그래밍 - 유석종 저 )을 참고하였습니다.