대부분의 알고리즘에서 사용하는 기본 자료구조
알고리즘에서 사용하는 데이터와 다음 노드를 가르키는 링크를 묶어서 노드로 정의하여 사용
C나 C++과 같은 프로그래밍 언어에서는 포인터(Pointer)의 개념으로 링크를 사용
파이썬에서 연결 리스트를 사용하기 위해서는 노드(Node)를 다음과 같이 클래스로 정의하여 사용
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
위 코드는 Node라는 이름의 클래스를 선언
이 클래스로 객체가 생성될때 init 메서드를 호출
이 Node클래스는 데이터를 저장하는 data와 링크를 저장하는 next를 멤버로 갖고 있음
연결 리스트는 자료를 저장하는 하나의 자료구조에 불과
기본적인 개념은 파이썬의 배열과 거의 동일
연결리스트의 장점은 곧 배열의 단점이 됨
배열은 연속된 메모리를 사용하지만 연결리스트는 반드시 연속적이라고 볼 수 없음
연결리스트는 연속적이지 않은 데이터들을 링크로 서로 연결하는 개념
총 4개의 노드가 연결된 연결리스트를 만들기
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_D = Node("D")
node_A.next = node_B
node_B.next = node_C
node_C.next = node_D
def print_list():
global node_A
node = node_A
while node:
print(node.data)
node = node.next
if __name__ == "__main__":
init_list()
print_list()
배열과 달리 연결 리스트는 각각의 노드가 링크로 연결
노드A -> 노드B -> 노드D -> 노드E
노드A -> 노드B -> 노드C -> 노드D -> 노드E
노드 B와 노드 D 사이에 노드 C를 삽입하기 위해서는
1. 새로 삽입되는 노드 C가 노드 D를 가르키도록하고,
2. 원래 노드 D를 가르키고 있던 노드 B가 노드 C를 가르키도록 해야함
# 노드 클래스 선언
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# 노드 초기화
def init_list():
# 생성할 노드_A를 전역으로 설정
# 노드A -> 노드B -> 노드D -> 노드E 구성
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):
# 전역 노드A사용
global node_A
# 앞 노드변수가 노드 A를 가르킴(포인터개념)
pre_node = node_A
# 다음 노드를 앞노드 변수의 다음노드로 가르킴
next_node =pre_node.next
# 만약 앞노드가 가르키는 노드에 데이터가 삭제할 데이터와 같다면
if pre_node.data == del_data:
# 노드 A에 다음 노드를 가르키도록함
node_A = next_node
# 앞 노드를 삭제
del pre_node
return
# 다음노드가 있다면 반복
while next_node:
# 다음노드의 데이터가 삭제할 데이터라면?
if next_node.data == del_data:
# 앞노드의 다음노드를 다음 노드의 다음으로 바꿈
# A->B->C가 있을때 A가 C를 가르키게 함
pre_node.next = next_node.next
# 그리고 B를 삭제
del next_node
break
# 앞노드를 다음 노드로 변경
pre_node = next_node
# 다음 노드를 다다음 노드로 변경
next_node = next_node.next
# 노드 추가
def insert_node(data):
# 전역 노드 A 사용
global node_A
# 새로운 노드 생성
new_node = Node(data)
# 새 변수 P와 T에 노드A를 가르키게 함
node_P = node_A
node_T = node_A
# 가르키는 변수T 데이터가 삽입되는 데이터보다 작거나 같다면 반복
while node_T.data <= data:
# 순회 시킴
node_P = node_T
node_T = node_T.next
# 새로운 노드의 포인터를 A -> B |여기에 들어갈것| -> D
# C노드가 D 노드를 가르키게 함
new_node.next = node_T
# B노드가 C노드를 가르키게 함
node_P.next = new_node
def print_list():
global node_A
node = node_A
while node:
print(node.data)
node = node.next
if __name__ == "__main__":
print("연결리스트 초기화 후")
init_list()
print_list()
print("노드 C를 추가한 후")
insert_node("C")
print_list()
배열을 사용하던 연결 리스트를 사용하던
데이터나 노드를 삽입하기 위해서는
삽입할 데이터의 위치 검색 과정과 실제 데이터를 삽입하는 과정이 필요
연결 리스트는 배열에 비해 시간의 효율성이 훨씬 높음
삽입할 데이터의 위치 검색 과정에서는 배열과 그 다지 차이가 없음
실제 데이터를 삽입하는 과정은
전체 배열의 크기와 연결 리스트의 노드의 수가 많으면 많을 수록 현격한 차이를 보여줌
# 노드 클래스 선언
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# 노드 초기화
def init_list():
# 생성할 노드_A를 전역으로 설정
# 노드A -> 노드B -> 노드D -> 노드E 구성
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):
# 전역 노드A사용
global node_A
# 앞노드변수가 노드 A를 가르킴(포인터개념)
pre_node = node_A
# 다음 노드를 앞노드의 다음노드로 가르킴
next_node =pre_node.next
# 만약 앞노드에 데이터가 삭제할 데이터와 같다면
if pre_node.data == del_data:
# 노드 A에 다음 노드를 넣음
node_A = next_node
# 앞 노드를 삭제
del pre_node
return
# 다음노드가 있다면 반복
while next_node:
# 다음노드의 데이터가 삭제할 데이터라면?
if next_node.data == del_data:
# 앞노드의 다음노드를 다음 노드의 다음으로 바꿈
# A->B->C가 있을때 A가 C를 가르키게 함
pre_node.next = next_node.next
# 그리고 B를 삭제
del next_node
break
# 앞노드를 다음 노드로 변경
pre_node = next_node
# 다음 노드를 다다음 노드로 변경
next_node = next_node.next
# 노드 추가
def insert_node(data):
# 전역 노드 A 사용
global node_A
# 새로운 노드 생성
new_node = Node(data)
# 새 변수 P와 T에 노드A를 가르키게 함
node_P = node_A
node_T = node_A
# 가르키는 변수T 데이터가 삽입되는 데이터보다 작거나 같다면 반복
while node_T.data <= data:
# 순회 시킴
node_P = node_T
node_T = node_T.next
# 새로운 노드의 포인터를 A -> B |여기에 들어갈것| -> D
# C노드가 D 노드를 가르키게 함
new_node.next = node_T
# B노드가 C노드를 가르키게 함
node_P.next = new_node
def print_list():
global node_A
node = node_A
while node:
print(node.data)
node = node.next
if __name__ == "__main__":
print("연결리스트 초기화 후")
init_list()
print_list()
print("노드 C를 추가한 후")
insert_node("C")
print_list()
print("노드 D를 삭제한 후")
delete_node("D")
print_list()
배열은 삽입 알고리즘과 마찬가지로 삭제한 후 삭제한 데이터 이후의 데이터들을 모두 앞으로 한 칸씩 이동해야 하는 반면에 연결 리스트는 링크를 끊어주고 삭제할 노드만을 헤제해주면 됨
시간적인 효율성은 배열보다 훨씬 좋다고 볼수 있음
코드의 효율성은 연결 리스트보다 배열이 좀더 낫다고 볼 수도 있음
배열의 경우에는 인덱스로 처리하기 떄문에
개념적으로 이해하기는 연결 리스트보다 배열이 더 쉬울수 있다.