Python 자료구조 [파이썬으로 구현한 알고리즘] (1) 연결 리스트(Linked List)

 연결리스트는 데이타를 담고있는 노드(node)와 각 노드를 연결하는 링크(link)로 구성 된다. 정적인 자료 구조인 배열과 달리 동적인 자료 구조이다. 연결리스트는 메모리가 필요하면 할당하고, 필요 없으면 해제하는 식의 메모리 관리가 가능하기 때문에 배열처럼 여분의 공간을 마련할 필요가 없어 메모리를 절약할 수 있는 이점이 있다.

연결리스트는 배열과 달리 메모리에 연속적으로 할당되지 않고 메모리상에 임의로 할당되고 흩어진 각 요소를 링크(link)에 의해 연결된다. 연결리스트는 각 노드별로 링크의 개수와 링크의 연결 상태에 따라  단순 연결 리스트, 환형 연결 리스트, 이중 연결리스트, 이중 환형 연결 리스트 등이 있다.

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

 단순 연결 리스트는 정보를 저장하는 노드와 바로 다음의 노드를 가리키는 링크 하나로 구성되어 있다. <그림 1>은 전형적인 단순 연결리스트의 모양이다.

< 그림 1. 전형적인 단순 연결 리스트의 형태 >

 노드를 class Node로 표현하여 노드 객체를 생성할 때 생성자에서 데이타를 넣는 멤버변수 self.data와 다음 노드를 가리키는 링크 self.next를 초기화 한다.

 노드를 여러개 생성하여, 각 노드에 임의의 값을 넣고, <그림 1>과 같은 연결리스트를 구성해 보자.

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com

 init_list() 함수에서 전역으로 노드를 생성하고, 각 노드의 링크를 다음 노드를 가리키게 한다. 즉, 연결 리스트가 생성 되었다! Main() 함수에서 생성된 연결 리스트를 while문으로 리스트를 따라 가면서 각 노드의 data를 출력한다. 파이썬은 변수의 자료형을 따로 지정하지 않는다. 그래서 <예제1>과 같이 같은 형태의 노드에 다양한 형태의 데이타를 넣을 수 있는 장점이 있다.

연결 리스트는 간단한 링크의 조작으로 노드의 삽입과 삭제가 가능하다.

< 그림 2. 단순 연결 리스트에서 노드를 삭제하기 위한 링크 변경 >

 

< 그림 3. 단순 연결 리스트에서 노드를 삽입하기 위한 링크 변경 >
 

 <그림 1>의 연결 리스트에서 노드를 삽입 하는 경우, 먼저 삽입 할 노드를 생성 한 뒤 <그림 3>과 같이 링크를 수정해 주면 된다. 연결 리스트에 노드를 삽입하는 함수를 구현해 보자.

  간단한 구현을 위해서 가장 앞부분에 새로운 노드를 생성 하였다. 이런 형태의 자료구조를 '스택'이라고 한다. 이에 대해서는 스택에 대해 알아볼때 좀더 자세히 알아보자. 전역 변수 node1은 가장 첫번째 노드를 가져야하므로 삽입된 원소를 node1로 바꾸어 주었다. 지금까지 배운 내용을 바탕으로 파이썬으로 연결 리스트를 생성하고, 노드를 삽입, 삭제하는 연산을 하는 프로그램을 만들어 보자.
 

환형 연결 리스트(Circular Linked List)

< 그림 4. 환형 연결 리스트 >
 

  파이썬으로 환형 연결 리스트 구현하려면 단순 연결 리스트 코드에서 마지막 노드의 링크가 첫번째 노드를 가리키도록 초기화 함수에 한줄만 추가 시켜주면 된다.
 

 

  def init_curlist():
    global node1, node2, node3, node4
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3.33333)
    node4 = Node("four")
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node1

 환형 리스트는 링크가 루프로 되어있으므로, 리스트에서 노드를 검색하거나 리스트를 출력할때, 무한 루프에 빠지지 않도록 주의 해야 한다.


이중연결 리스트(Doubly Linked List)
 
 단순 연결 리스트가 다음 번 노드를 가리키는 링크만 가진다면, 이중 연결 리스트는 이전 노드를 가리키는 노드와 다음 노드를 가리키는 링크, 2개의 링크가 존재 한다. 앞뒤 노드 링크를 모두 가지고 있기 때문에, 단순 연결리스트보다 유연하게 동작한다.
 

< 그림 5. 이중 연결 리스트>
 

 이중 연결 리스트의 노드를 파이썬으로 표현하려면 이전 노드를 가리키는 링크를 추가 시켜주면 된다.
 

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

 이중 연결 리스트는 링크가 하나 더 추가되었기 때문에, 삽입/삭제에 총 네개의 링크를 조작해야 한다. 이중 연결 리스트에서 노드를 삭제하는 동작을 보도록 하자.
 

< 그림 6. 이중 연결 리스트에서 노드를 삭제하기 위한 링크 변경 >
 

  <그림 6>에서 검은색 노드를 삭제하고자 할때, 이전 노드와 다음 노드의 링크를 <그림 6>와 같이 변경해야 한다. 이중 연결 리스트의 삭제 함수를 구현해 보자.
 

def delete_dnode(del_data):
    global dnode1
    dnode = dnode1
    while dnode:
        if dnode.data == del_data:
           dnode.prev.next = dnode.next
           dnode.next.prev = dnode.prev
           del dnode
           break
        dnode = dnode.next      

 
  삭제 할 노드의 이전 노드의 다음 노드를 가리키는 링크를 삭제 할 노드의 다음 노드를 가리키게 하고, 삭제 할 노드의 다음 노드의 이전 노드를 가리키는 링크를 삭제 할 노드의 이전 노드를 가리키게 한다.
 이번에는 이중 연결 리스트의 삽입 함수를 구현해 보자.
 

def insert_dnode(ins_data):
    global dnode1
    new_dnode = DNode(ins_data)
    new_dnode.next = dnode1
    dnode1.prev = new_dnode
    dnode1 = new_dnode

 단순 연결 리스트의 경우와 마찬가지로 연결 리스트의 첫번째에 새로운 노드를 삽입을 하도록 구현하였다. 새로운 노드를 생성하고 새로운 노드의 다음 노드 가리키는 링크를 연결 리스트의 첫번째 노드로 하고,  연결 리스트의 첫번째 노드의 이전 노드를 가리키는 링크를 새로운 노드를 가리키게 한다. 그리고 새로 생성된 노드가 첫번째 노드로 바꾸어 준다. 지금은 링크 2개만 조작하고 나머지 링크 2개는 기본 값(None)을 넣는다. 하지만 연결 리스트의 중간에 새로운 노드를 추가하고자 한다면 4개의 링크를 모두 조작해야 한다.
 

 

< 그림 7. 이중 연결 리스트의 가장 앞에 노드를 삽입하기 위한 링크 변경 >

 

 마지막으로 이중 연결 리스트에서 생성/삽입/삭제/출력 하는 예제를 파이썬으로 작성해보고 연결 리스트에 대한 내용을 마무리 하도록 하겠다.
 

#!/usr/bin/python
class DNode:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next

def init_dlist():
    global dnode1
        dnode1 = DNode(1)
        dnode2 = DNode(2)
        dnode3 = DNode(3.33333)
        dnode4 = DNode("four")
        dnode1.next = dnode2
        dnode2.prev = dnode1
        dnode2.next = dnode3
        dnode3.prev = dnode2
        dnode3.next = dnode4
        dnode4.prev = dnode3

def delete_dnode(del_data):
    global dnode1
    dnode = dnode1
    while dnode:
        if dnode.data == del_data:
            dnode.prev.next = dnode.next
            dnode.next.prev = dnode.prev
            del dnode
            break
        dnode = dnode.next

def insert_dnode(ins_data):
    global dnode1
    new_dnode = DNode(ins_data)
    new_dnode.next = dnode1
    dnode1.prev = new_dnode
    dnode1 = new_dnode

def print_dlist():
    global dnode1
    dnode = dnode1
    while dnode:
        print dnode.data,
        dnode = dnode.next
    print

def Main():
    init_dlist()
    delete_dnode(4)
    insert_dnode(5)
    print_dlist()
Main()

< 예제 3. 이중 연결 리스트 생성과 노드 삽입/삭제 연산 >