[Python] 연결 리스트(Linked List)

 

연결 리스트는 대부분의 알고리즘에서 사용하는 기본 자료구조이다. 알고리즘에서 사용하는 데이터와 다음 노드를 가리키는 링크를 묶어서 노드로 정의하여 사용한다. C/C++에서는 포인터(Pointer) 개념으로 링크를 사용하지만 파이썬은 포인터라는 개념이 없을뿐더러 필요하지도 않다.

<노드(Node)와 링크(Link)> 

파이썬에서는 연결 리스트를 사용하기 위해 노드(Node)를 다음과 같이 클래스로 정의하여 사용한다.

class Node:
    def __init__(self, data, next=None):
        self.data = data  # 데이터 저장
        self.next = next  # 링크 저장

위의 코드는 Node라는 이름의 클래스를 선언하여 이 클래스로 객체가 생성될 때 __init__ 메서드를 호출한다. 이 Node 클래스는 데이터를 저장하는 data와 링크를 저장하는 next를 멤버로 갖고 있다. 연결 리스트를 그림으로 표현하면 아래와 같다.

 

<연결 리스트의 특징> 

배열 대신에 연결 리스트를 사용하는 이유를 생각해보면 연결 리스트의 장점은 곧 배열의 단점이 되는 것을 알 수 있다. 배열은 동일한 자료형을 갖는 데이터의 집합이며, 그 특성은 연속적이다. 배열을 생성할 때 한 번에 총메모리를 확보하여 사용할 수 있도록 하기 때문에 프로그램이 실행되는 중간에 배열의 크기를 바꾸거나 할 수가 없다. 

따라서 배열의 단점은 배열 안에 저장되어 있는 값들을 정렬할 때도 일일이 메모리에 저장되어 있는 값을 바꾸어 주어야 한다. 연결 리스트는 이와 같은 배열의 단점을 해결해준다.

배열은 연속된 메모리를 사용하지만 연결 리스트는 반드시 연속적이라고는 볼 수 없다. 오히려 연결 리스트는 연속적이지 않는 데이터들을 링크로 서로 연결하는 개념이라고 볼 수 있다.

 

<연결 리스트 초기화> 

class Node:
    def __init__(self, data, next=None):
        self.data = data  # 데이터 저장
        self.next = next  # 링크 저장

# 연결 리스트 초기화 작업
def init_list():
    global node_A
    # 4개의 노드를 생성
    node_A = Node("A")
    node_B = Node("B")
    node_C = Node("C")
    node_D = Node("D")
    # 각각의 노드에 데이터를 저장한 후에 각 노드를 링크로 연결
    node_A.next = node_B
    node_B.next = node_C
    node_C.next = node_D


def print_list():  # node 데이터 print
    global node_A
    node = node_A
    while node:
        print(node.data)
        node = node.next
    print


if __name__ == '__main__':
    print("연결 리스트 초기화 후")
    init_list()
    print_list()

 

 

<연결 리스트의 삽입 알고리즘> 

class Node:
    def __init__(self, data, next=None):
        self.data = data  # 데이터 저장
        self.next = next  # 링크 저장

# 연결 리스트 초기화 작업
def init_list():
    global node_A
    # 4개의 노드를 생성
    node_A = Node("A")
    node_B = Node("B")
    node_D = Node("D")
    node_E = Node("E")
    # 각각의 노드에 데이터를 저장한 후에 각 노드를 링크로 연결
    node_A.next = node_B
    node_B.next = node_D
    node_D.next = node_E


def insert_node(data):  # 삽입할 데이터를 인수로 받는다
    global node_A
    new_node = Node(data)
    node_P = node_A
    node_T = node_A
    while node_T.data <= data:  
        node_P = node_T
        node_T = node_T.next
    new_node.next = node_T
    node_P.next = new_node


def print_list():  # node 데이터 print
    global node_A
    node = node_A
    while node:
        print(node.data)
        node = node.next
    print


if __name__ == '__main__':
    print("연결 리스트 초기화 후")
    init_list()
    print_list()
    print("노드 C를 추가한 후")
    insert_node("C")
    print_list()

노드를 삽입하는 insert_node() 함수는 인수로 data를 받는다. 다음으로 node_A를 global로 선언한다. 이 global인 node_A는 이미 init_list() 함수에서 생성된 연결 리스트의 첫 번째 노드인 node_A 값을 갖고 있다.

그러고 나서 인수로 받은 data를 저장할 new_node를 선언한다. node_T와 node_P는 연결 리스트를 탐색하면서 새로운 노드를 삽입할 노드의 위치를 보관하기 위해 선언한 변수들이다.

node_T.data가 인수로 받은 data보다 크게 되면, 해당 위치가 인수로 받은 data를 사용하여 생성한 new_node가 삽입될 위치가 된다. 새롭게 삽입할 노드인 new_node의 next는 현재 node_T를 가리키도록 하고, node_T의 이전 노드에 해당하는 node_p의 next에는 새롭게 추가될 new_node를 저장한다.

 

- 삽입 알고리즘의 분석 -

1. 시간 효율성

배열을 사용하던 연결 리스트를 사용하던 데이터나 노드를 삽입하기 위해서는 삽일할 데이터의 위치 검색 과정과 실제 데이터를 삽입하는 과정이 필요한데, 연결 리스트는 배열에 비해 시간의 효율성이 훨씬 높다. 삽입할 데이터 위치 검색 과정은 배열과 그다지 차이점이 없지만, 실제 데이터를 삽입하는 과정은 전체 배열의 크기와 연결 리스트의 노드의 수가 많으면 많을수록 현격한 차이가 나타날 것이다.

2. 공간의 효율성

배열은 실제 프로그래밍에서 사용할 때 프로그램의 실행 중에 배열의 크기를 변경시키지 못하기 때문에 공간의 효율성이 떨어진다. 하지만 연결 리스트는 언제든지 필요할 때 동적으로 공간(메모리)을 할당하여 사용할 수 있으므로 배열에 비해 공간의 효율성이 뛰어나다고 할 수 있다.

3. 코드의 효율성

코드의 효율성은 연결 리스트보다 배열이 조금 더 낫다고 볼 수도 있다. 배열의 경우 for문에서 사용하는 것처럼 배열의 인덱스만으로도 가능하기 때문에 코드를 작성할 때도 간단하고, 코드를 이해하기도 훨씬 수월하다. 그에 비해서 연결 리스트의 코드는 포인터와 구조체로 되어 있기 때문에 이해하기 어려울 수 있다.

 

<연결 리스트의 삭제 알고리즘> 

 

1. 첫 번째 노드를 삭제하는 경우

 

 

2. 두 번째 이상의 노드를 삭제하는 경우

class Node:
    def __init__(self, data, next=None):
        self.data = data  # 데이터 저장
        self.next = next  # 링크 저장

# 연결 리스트 초기화 작업
def init_list():
    global node_A
    # 4개의 노드를 생성
    node_A = Node("A")
    node_B = Node("B")
    node_D = Node("D")
    node_E = Node("E")
    # 각각의 노드에 데이터를 저장한 후에 각 노드를 링크로 연결
    node_A.next = node_B
    node_B.next = node_D
    node_D.next = node_E


def insert_node(data):  # 삽입할 데이터를 인수로 받는다
    global node_A
    new_node = Node(data)
    node_P = node_A
    node_T = node_A
    # 연결 리스트의 노드 탐색
    while node_T.data <= data:
        node_P = node_T
        node_T = node_T.next
    # 링크 연결
    new_node.next = node_T
    node_P.next = new_node


def delete_node(del_data):  # 삭제할 데이터를 인수로 받는다
    global node_A
    pre_node = node_A
    next_node = pre_node.next

    # 첫번째 노드를 삭제하는 경우
    if pre_node.data == del_data:
        node_A = next_node
        del pre_node
        return

    # 두번째 이상의 노드를 삭제하는 경우
    while next_node:  # next_node 가 존재할 때
        if next_node.data == del_data:
            pre_node.next = next_node.next
            del next_node
            break
        pre_node = next_node
        next_node = next_node.next


def print_list():  # node 데이터 print
    global node_A
    node = node_A
    while node:
        print(node.data)
        node = node.next
    print


if __name__ == '__main__':
    print("연결 리스트 초기화 후")
    init_list()
    print_list()
    print("노드 C를 추가한 후")
    insert_node("C")
    print_list()
    print("노드 D를 삭제한 후")
    delete_node("D")
    print_list()

삽입 알고리즘과 동일하게 global로 node_A를 선언한 연결 리스트를 사용한다. 이 연결 리스트를 가리키는 노드로 pre_node를 선언하고, pre_node의 다음 노드에 해당하는 pre_node.next를 next_node로 선언한다.

삭제할 del_data와 연결 리스트의 첫 번째 노드인 pre_node.data가 같다면 node_A에 next_node를 저장하고 현재 노드인 pre_node를 삭제한 후에 delete_node() 함수를 리턴한다.

만약 첫 번째 노드에 삭제할 데이터가 없다면 두 번째 단계인 "삭제할 데이터 찾기"를 하기 위해 while문을 실행한다.

현재의 연결 리스트를 가리키는 next_node가 존재하는 동안 위의 while문은 반복된다. next_node의 data가 인수로 받은 삭제할 데이터인 del_data와 같다면, next_node인 다음 노드를 가리키는 링크를 이전 노드인 pre_node의 next에 저장하고, next_node를 삭제한 후에 리턴한다.

그러나, 현재 노드를 가리키는 next_node.data가 인수로 받은 del_data와 같지 않다면, 이전 노드인 pre_node는 현재 노드인 next_node를 가리키도록 하고, next_node는 다음에 해당하는 next_node.next를 가리키도록 한다.

 

C/C++ 프로그래밍 언어를 사용할 때는 malloc()과 같이 별도의 메모리 할당 함수를 사용하여 노드를 생성하거나 삭제할 때도 별도의 메모리 삭제 함수를 사용해야 하지만, 파이썬에서는 간단한 del이라는 키워드로 객체를 삭제하면 그만이다.

 

- 삭제 알고리즘의 분석 -

1. 시간 효율성

연결 리스트의 삽입 알고리즘과 마찬가지로 삭제 알고리즘도 삭제할 노드를 검색하는 과정과 찾은 노드를 삭제하는 과정이 필요하다. 노드를 삭제하는 경우에 배열은 삽입 알고리즘과 마찬가지로 삭제한 후 삭제한 데이터 이후의 데이터들을 모두 앞으로 한 칸씩 이동해야 하는 반면 연결 리스트는 링크를 끊어주고 삭제할 노드만을 해제해주면 된다. 따라서 시간적인 효율성은 배열보다 훨씬 좋다고 볼 수 있다.

2. 공간의 효율성

배열에 비해 연결 리스트는 삽입 알고리즘과 마찬가지로 메모리를 할당하고, 삭제한 메모리를 해제하기 때문에 공간적인 효율성이 높다고 볼 수 있다.

3. 코드의 효율성

배열의 경우에는 인덱스로 처리하기 때문에 연결 리스트보다 배열이 더 효율적이라고 볼 수 있다.