(단방향)연결리스트
자료구조에서 연결리스트란?
연결리스트는 차례로 연결된 노드를 표현해주는 자료구조입니다. 단방향 연결리스트에서 각 노드는 다음 노드를 가리키는 특징을 가집니다. 반면 이름에서도 알 수 있듯이, 양방향 연결리스트에서의 각 노드들은 다음 노드와 이전 노드를 함께 가리킵니다.
배열과는 달리 연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없는 단점을 가집니다. 연결리스트에서 N번째 노드를 찾고 싶다면 시작노드(헤드노드)부터 N번의 반복을 수행한 후 찾을 수 있습니다.
반면에, 연결리스트의 장점은 연결리스트의 시작노드에서 아이템을 추가하거나 시작노드를 삭제하는 연산을 상수 시간에 할 수 있다는 점이 있습니다. 이런 점은 특정 애플리케이션에서 굉장히 유용할 수 있습니다.
상수 시간의 의미 - 상수 시간의 big-O 표기 : O(1)
Python으로 구현하는 연결리스트
연결리스트의 노드
연결리스트에서 각각 데이터를 담고 또 다음 데이터를 담고있는 노드에 대한 정보를 담고있는 형태를 노드(Node)라고 일컫습니다.
단방향 연결리스트에서는 노드가 표현 혹은 담고있는 데이터와 노드가 속한 연결리스트의 관점에서 다음노드에 대한 정보를 담고 있습니다. 단방향 연결리스트에서 특정노드의 위치를 정확히 알고있는 주체는 특정 노드의 이전노드 뿐입니다. (헤드노드는 예외 - 헤드노드는 시작노드이므로 자명히 알게됩니다)
헤드노드는 자신의 다음노드에 대한 정보만을 알고있고, 헤드노드 다음노드는 자신의 다음노드에 대한 정보만 알고 있습니다. 이 패턴의 반복을 통해 연결리스트가 완성됩니다.
연결리스트의 노드의 Python 구현
class LinkedListNode:
def __init__(self, input_data):
# 다음 노드에 대한 정보를 담는 인스턴스 변수
# 다음 노드 지정은 선언 후 이루어집니다
self.next_node = None
# 노드 인스턴스가 담을 데이터
self.data = input_data
# 노드가 소속된 연결리스트에 가장 뒤에 받은 데이터를 담는 새로운 노드를 추가하는 함수
def append_to_tail(self, input_data):
# 입력 받은 데이터를 생성해 end_node라는 변수에 할당
end_node = LinkedListNode(input_data)
# 루프동안 체크할 노드를 담을 temp_next를 선언 후 노드 자신을 할당
temp_next = self
while temp_next.next_node != None: # 자신이 가장 마지막 노드가 아니라면 루프 진행
temp_next = temp_next.next_node # temp_nnext를 temp_next.next_node로 할당해 다음 연결을 체크
# 마지막 노드까지 진행되면 루프가 멈추고 temp_next에 현재까지 가장 마지막 노드가 할당됨
temp_next.next_node = end_node # 가장 마지막 노드의 next_node에 위에서 새로 생성한 노드를 연결해주고 함수 끝
# 입력받은 노드를 자신의 다음 노드로 지정하는 함수
# (연결리스트 시작점에 새로운 헤드노드를 할당시 사용)
def point_next_node(self, input_node):
self.next_node = input_node
노드 Class를 이용한 연결리스트 Class의 Python 구현
class LinkedList:
def __init__(self, head_data):
# 연결리스트 정의부터 헤드노드를 인스턴스 변수로 할당
# 연결리스트 정의때 입력받는 데이터는 헤드노드가 담고있을 데이터입니다
self.head_node = LinkedListNode(head_data)
# 입력받은 데이터를 담고있는 노드를 연결리스트에서 삭제하는 함수
def delete_node(self, input_data):
# 헤드노드 부터 시작해 여러노드를 점검하기 위해 임시로 할당할 변수 선언 및 헤드노드 할당
temp_node = self.head_node
if (temp_node.data == input_data): # 루프전, 조건 입력받은 데이터와 현재 체크하는 노드의 데이터가 같은가
self.head_node = temp_node.next_node # 루프전이기 때문에 헤드노드를 삭제하는 조건
return # 링크드리스트의 헤드노드를 헤드노드의 다음 노드로 지정하고 함수 리턴
while temp_node.next_node != None: # 마지막 노드가 아니면 루프 진행
if temp_node.next_node.data == input_data: # 체크노드 다음노드의 데이터와 입력 데이터 확인
temp_node.next_node = temp_node.next_node.next_node # 위 조건 성립시 현재 체크노드의 다음노드를 다음노드의 다음노드로 지정
return # 함수 리턴
temp_node = temp_node.next_node # 루프 진행동안은 다음노드를 체크하기 위해 임시 변수를 다음 노드로 할당
# 연결리스트에서 마지막 노드 다음노드로 새로운 노드를 추가하는 메소드
def append_to_tail(self, input_data):
# 노드 클래스의 메소드를 이용하여 간단히 구현가능
self.head_node.append_to_tail(input_data)
# 연결리스트에서 헤드보다 앞에 새로운 노드를 추가하는 메소드
def append_to_head(self, input_data):
# 새로운 노드 정의
new_head_node = LinkedListNode(input_data)
# 새로운 노드에게 현재 헤드노드를 다음노드로 가리키도록 지정
new_head_node.point_next_node(self.head_node)
# 연결리스트의 헤드노드를 새로운 노드로 지정
self.head_node = new_head_node