DataStructure in Python[연결리스트]

출처 : http://onestep.tistory.com/33

1. 연결리스트(Linked List)

연결리스트는 노드(node)와 링크(link)로 구성된다.

노드는 데이터를 담고 링크는 각 노드를 연결한다.

연결리스트는 메모리가 필요하면 할당, 필요없으면 해제하는 식으로 메모리 관리가 가능하기 때문에 배열처럼 여분의 공간을 마련할 필요가 없어 메모리를 절약할수 있다.

연결리스트는 배열처럼 메모리에 연속적으로 할당되지 않고 임의로 할당된 뒤에 각 요소들을 링크로 연결한다. 

연결리스트는 각 노드별로 링크의 개수와 링크의 연결 상태에 따라 단순연결리스트, 환형 연결 리스트, 이중 연결리스트, 이중 환형 연결리스트 등이 있다.

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

단순 연결 리스트는 정보를 저장하는 노드와 바로 다음 노드를 가리키는 링크하나로 구성된다.

파란색 : 데이터가 들어가는 부분

하얀색 : 다음 노드를 가리키는 링크

단순 연결리스트는 사용자가 첫번째 노드를 알고 있어야 연결 리스트에 진입할수 있으며 마지막 노드는 아무것도 가리키지 않게 한다.

파이썬2 로 구현한 SimpleLinkedList

# 파이썬 버전 2.7
 
# 노드를 classNode로 표현하였다.
# 데이터를 담는 멤버변수 self.data
# 링크를 담는 멤버 변수 self.next 를 초기화 한다.
 
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
# init_list() 함수에서 전역으로 노드를 생성하고 각 노드의 링크를 다음 노드를 가리킨다.
def init_list():
    global node1, node2, node3, node4
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3.333)
    node4 = Node("four")
    node1.next = node2
    node2.next = node3
    node3.next = node4
 
def Main():
    init_list()
    node = node1
    print node, node1, node2, node3, node4
    while node:
        print node.data
        node = node.next
 
Main()

실제 실행을 해보면 다음과 같이 생성되는 것을 볼수 있다.

파이썬은 변수의 자료형을 따로 지정하지 않기 때문에 노드에 다양한 형태의 데이타를 넣을수 있는 장점이 있다.

1.2 단순연결리스트 삭제

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

검은색 노드를 삭제 하고 싶을때 이전노드의 링크를 다음 노드를 가리키게 링크를 변경하고 삭제할 노드를 메모리에서 해제하면 삭제가 완료된다.

def delete_node(del_data):
    global node1
    pre_node = node1
    next_node = pre_node.next
 
    if pre_node.data == del_data:
        node1 = next_node
        del pre_node
        # pre_node의 타입은 instance이다.
        # del => 리스트, 리스트 요소를 삭제하는 명령어.
        # 참고로 한글 주석이라서 그대로 복붙하면 에러날수 있으니 주의
        return node1
 
    while 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
    return node1

각 노드에 전체 자료가 다 들어가 있는게 아니라 각 노드는 주소만 가지고 있을 뿐이다.

node1에는 객체에 대한 주소가 들어가 있으며 그 주소를 통해 값을 참조한다.

만약 동일 객체의 주소를 받은 다른 변수가 있어 그 변수에서 해당 주소 값으로 타고 들어가서 값을 수정하면 

node1또한 그 값이 변화하게 되는 것이다.

1.3 단순연결리스트 추가

추가할 노드를 생성한 뒤 링크를 수정하면 된다.

가장 앞부분에 새로운 노드를 생성, 이런 형태의 자료구조를 스택이라고 한다.

(추가되는 새로운 자료를 간편함을 위해 제일 앞부분에 추가되도록 했다한다.)

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
def init_list():
    global node1, node2, node3, node4
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3.333)
    node4 = Node("four")
    node1.next = node2
    node2.next = node3
    node3.next = node4
 
def delete_node(del_data):
    global node1
    pre_node = node1
    next_node = pre_node.next
 
    if pre_node.data == del_data:
        node1 = next_node
        del pre_node
        #Type of pre_node is instance
        # del can delete list or a list item
        return node1
    while 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
    return node1
 
def insert_node(ins_data):
    global node1
    new_node = Node(ins_data)
    new_node.next = node1
    node1 = new_node
    return node1
 
def print_list():
    global node1
    node = node1
    while node:
        print node.data
        node = node.next
 
def Main():
    init_list()
    print_list()
    node = delete_node(2)
    print "after delete","===="*20
    print_list()
    node = insert_node(1000000000)
    print "after delete","===="*20
    print_list()
 
Main()

1.4 환형 연결 리스트(Circualr Lined List)

이것은 단순 연결리스트의 마지막 노드 링크가 첫번째 노드를 가리키는 형태를 말한다. 환형 연결 리스트는 임의의 노드에서 모든 노드에 접근이 가능하다.

만드는 방법은 마지막 노드가  첫번째 노드를 가리키도록 초기화를 행하면 된다. 다만 이렇게 되면 링크가 루프가 되어있기 때문에노드 검색, 리스트 출력할 때 무한 루프에 빠지지 않도록 주의해야한다.

 
#-*- coding: UTF-8 -*-
import re
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

 
 
 
def init_list():
    global node1, node2, node3, node4
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3.333)
    node4 = Node("four")
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node1  <======= 다시 처음으로 연결
    # circular linked list
    # 이걸 while문으로 출력하게 하면 무한 루프를 돌게 된다.
 
def delete_node(del_data):
    global node1
    pre_node = node1
    next_node = pre_node.next
 
    if pre_node.data == del_data:
        node1 = next_node
        del pre_node
        #Type of pre_node is instance
        # del can delete list or a list item
        return node1
    while 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
    return node1
 
def insert_node(ins_data):
    global node1
    new_node = Node(ins_data)
    new_node.next = node1
    node1 = new_node
    return node1
 
def print_list():
    global node1
    node = node1
    while node:
        print node.data
        node = node.next
 
def Main():
    init_list()
    print_list()
    node = delete_node(2)
    print "================== after delete","===="*20
    print_list()
    node = insert_node(1000000000)
    print "================== after insert","===="*20
    print_list()
 
Main()
 
 
 
 

1.5 이중 연결 리스트(Doubly Lined List)

이중연결 리스트는 이전 노드를 가리키는 노드와 다름 노드를 가리키는 링크, 2개의 링크가 존재한다.

앞뒤 노드 링크를 모두 가지고 있어서 단순 연결 리스트보다 유연하게 동작한다.

1.6 이중 연결 리스트 삭제

1.7 이중 연결 리스트 추가

아래의 코드는 생성, 삭제, 추가를 전부 포함한 코드이다.

#-*- coding: UTF-8 -*-
import re
class Node:
    def __init__(self, data, next=None, pre = None):
        self.data = data
        self.next = next
        self.pre = pre
 
def init_list():
    global node1, node2, node3, node4
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3.333)
    node4 = Node("four")
 
    node2.pre = node1
    node3.pre = node2
    node4.pre = node3
 
    node1.next = node2
    node2.next = node3
    node3.next = node4
 
def delete_node(del_data):
    global node1
    pre_node = node1
    next_node = pre_node.next
    next_node.pre = pre_node
 
    if pre_node.data == del_data:
        node1 = next_node
        next_node.pre = node1
        del pre_node
        #Type of pre_node is instance
        # del can delete list or a list item
        return node1
    while next_node:
        if next_node.data == del_data:
            pre_node.next=next_node.next
            next_node.next.pre = pre_node
            del next_node
            break
 
        pre_node = next_node
        next_node.pre = pre_node
        next_node=next_node.next
 
    return node1
 
def insert_node(ins_data):
    global node1
    new_node = Node(ins_data)
    new_node.next = node1
    node1.pre = new_node
    node1 = new_node
    return node1
 
def print_list():
    global node1
    node = node1
    while node:
        print node.data
        node = node.next
 
def Main():
    init_list()
    print_list()
    node = delete_node(2)
    print "=========================================== after delete","===="*20
    print_list()
    node = insert_node(1000000000)
    print "=========================================== after insert","===="*20
    print_list()
 
Main()
 
 
 
 

이중연결의 경우에는 앞,뒤로는 2개의 링크 조작을 하면되지만 중간에 할경우에는 링크 조작을 총 4개를 행해야 한다.