[필수알고리즘, python] 연결 리스트(Linked list)

필수알고리즘

• 연결 리스트(Linked list)

알고리즘 설명

연결리스트는 알고리즘과 자료구조 중에서 가장 기본이 되며, 가장 많이 사용되는 알고리즘에 속한다. 연결리스트에는 기본적으로 노드(Node)와 링크(Link)라는 용어를 사용하게 되는데, 

각각의 노드(Node)들은 내부에 1. data 2. 연결된 노드의 정보인 링크(Link)를 가지고 있다.

 

왜 배열을 사용하지 않고, 연결리스트를 사용할까?

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

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

연결리스트는 이와같은 배열의 단점을 해결해준다.

 

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

 

 

(1) init_list()

 

 

(2) insert_list()

 

(3) delete_list()

 

소스 코드

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
def init_list():
    global node_A
    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 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:
        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 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 = 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()