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

연결 리스트는 데이터와 다음 노드를 가리크는 링크를 묶어서 노드로 정의하여 사용하는 알고리즘이다.

순서가 있는 데이터 묶음이라는 점에서 배열과 유사하다고 생각할 수도 있다.

 

배열은 한 번 생성시 총 메모리를 확보해 프로그램 실행 중간에 크기를 변경할 수 없고

배열 안의 값을 정렬할 때에도 하나씩 메모리에 저장되어 있는 값을 바꿔주어야 한다.

 

하지만 연결 리스트는 배열과는 다르게 연속적이지 않은 데이터들을 링크로 서로 연결해줌으로써

배열이 가지는 단점을 보완할 수 있다.

 

1. 노드(Node) 정의하기

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

노드를 클래스로 정의할 때, 노드의 데이터인 data를 지정해주고 다음 노드를 가리키는 링크를 저장하는 next 멤버를 지정해준다.

 

2. 연결 리스트 초기화하기

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_C = Node("C")
    node_A.next = node_B
    node_B.next = node_C

노드 객체 A, B, C를 생성한 뒤, 각 노드의 next 멤버에 다음 노드 객체를 넣어준다.

 

3. 연결 리스트 삽입하기

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_C = Node("C")
    node_A.next = node_B
    node_B.next = node_C
    
def insert_node(data):
    global node_A
    new_nodw = Node(data)
    node_P = node_A
    node_T = node_A.next
    new_node.next = node_T
    node_P.next = new_node

insert_node라는 함수는 data를 인수로 받고 이 값을 저장하는 new_node를 선언하게 된다.

그리고 새로운 노드를 삽입할 노드의 위치를 얻기 위해 node_P, node_T를 내부 변수로 선언한다.

새로 삽입할 노드(new_node)의 next는 현재 node_T를 가리키도록 하고 node_T의 이전 노드인 node_P의 next에는 새롭게 추가될 new_node를 넣어준다.

 

4. 연결 리스트 삭제하기

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

delete_node 함수는 인수로 del_data를 받는다.

연결 리스트를 가리키는 pre_node를 선언하고 pre_node의 다음인 pre_node.next를 next_node로 선언한다.

삭제할 노드인 del_data와 pre_node.data가 같다면 삭제할 노드가 가장 첫 번째 노드이므로

node_A에 next_node를 지정하고 현재 노드인 pre_node를 삭제한다. 그 후 delete_node() 함수를 리턴한다.

삭제할 노드가 첫 번째 노드가 아니라면 현재 연결 리스트를 가리키는 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를 가리키도록 한다.

 

5. 연결 리스트 알고리즘 분석하기 (배열과 비교하기)

삽입 알고리즘

1) 시간 효율성: 연결 리스트와 배열 보두 데이터를 삽입하기 위해서는 위치 검색 과정과 데이터 삽입 과정이 필요하다.

위치 검색 과정에서는 배열과 연결 리스트가 큰 차이가 없지만, 데이터 삽입 과정에서 배열은 삽입 후 이후 데이터들을 한 칸씩 이동해야 하지만 연결 리스트는 가리키는 링크만 수정하면 되므로 연결 리스트 알고리즘이 더 좋은 효율을 보여준다.

2) 공간 효율성: 배열은 프로그램 실행 중 크기를 고정시키기 때문에 공간 효율성이 떨어지고 연결 리스트는 떨어져있는 

데이터들을 가리키기만 하면 되기때문에 동적으로 공간을 할당할 수 있어 효율성이 뛰어나다.

3) 코드 효율성: 코드를 사용할 때는 배열은 인덱스를 이용하여 데이터에 접근할 수 있기 때문에 코드 효율성은 배열이 더 낫다고 볼 수 있다.

 

삭제 알고리즘

1) 시간 효율성: 데이터를 삭제할 때도 위치 검색 과정과 데이터 삭제 과정이 필요하다. 배열은 데이터 삭제 이후에 데이터들을 한 칸씩 앞으로 이동시켜야 하지만 연결 리스트를 링크를 끊어주기만 하면 되기 때문에 시간 효율성은 연결 리스트가 더 낫다.

2) 공간 효율성: 삽입 알고리즘과 마찬가지로 연결 리스트의 공간 효율성이 더 낫다.

3) 코드 효율성: 삽입 알고리즘과 마찬가지로 배열은 인덱스를 사용할 수 있기 때문에 코드 효율성은 배열이 더 낫다.

 

 

---

[참고 문헌]

 

1. 위키백과, "연결 리스트", https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

2. 박선주, 영진닷컴, "필수 알고리즘 with 파이썬