프로그래밍/자료구조 && 알고리즘
[Python] 링크드 리스트(Linked List)
코드몬스터
2022. 9. 18. 23:27
728x90
💡 본 내용은 코드잇 기본 자료구조들 강의 및 신찬수 교수님의 자료구조 강의를 들고 요약한 내용입니다.
내용이 부족하거나 잘 못 될 수 있습니다.
추후 계속 공부하면서 수정하겠습니다~!!
링크드 리스트(Linked List)
- 데이터를 순서대로 저장해준다.
- 요소를 계속 추가할 수 있다.(동적 배열처럼)
연결된 박스(노드)들의 순서:
규리 → 태호 → 동욱 →유나 → 현승
👉프로그래밍적으로 생각
노드(Node): 데이터와 Next 의 객체이다.
연속적으로 되어 있는 것이 아닌 실제 메모리에는 ★흩어져★ 있다.
# ------------- 간단한 링크 노드 -------------------
class Node:
"""링크드 리스트의 노드 클래스"""
def __init___(self, data):
self.data = data # 노드가 저장하는 데이터
self.next = None # 다음 노드에 대한 레퍼런스
# 데이터 2, 3, 5, 7, 11을 담는 노드들 생성
# 지금은 각 노드끼리 아무런 관계가 없다.
head_node = Node(2)
node_1 = Node(3)
node_2 = Node(5)
node_3 = Node(7)
tail_node = Node(11)
# -------------- 간단한 링크드 리스트 -------------------
# 노드 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node
# 노드 순서대로 출력
iterator = head_node
while iterator is not None:
print(iterator.data)
iterator = iterator.next
# ---------------- 링크드 리스트 클래스 및 추가 연산 ---------------------
# 헤드에 해당하는 노드가 고정되면 더 이상 변동 X
# tail은 뒤이어 추가되는 노드로 변동
# tail.next(해당 노드의 next)는 다음 노드를 가리키고 있다.
class Node:
"""링크드 리스트의 노드 클래스"""
def __init___(self, data):
self.data = data # 노드가 저장하는 데이터
self.next = None # 다음 노드에 대한 레퍼런스
class LinkedList:
"""링크드 리스트 클래스"""
def __init__(self):
self.head = None
self.tail = None
def append(self, data): # 인스턴스 메소드
"""링크드 리스트 추가 연산 메소드"""
new_node = Node(data)
if self.head is None: # 인스턴스 헤드가 None 이면(비어있으면)
self.head = new_node
self.tail = new_node
else: # 링크드 리스트가 비어있지 않으면
self.tail.next = new_node
self.tail = new_node
# 새로운 링크드 리스트 생성
my_list = LinkedList()
# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)
# 링크드 리스트 출력
iterator = my_list.head
while iterator is not None:
print(iterator.data)
iterator = iterator.next
👉링크드 리스트 __str__ 메소드
def __str__(self) -> str:
"""링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
res_str = "|"
# 링크드 리스트 안에 모든 노드를 돌기 위한 변수
# 가장 앞 노드로 정의
iterator = self.head
# 링크드 리스트 끝까지 돈다.
while iterator is not None:
# 각 노드의 데이터를 리턴하는 문자열에 더 해준다.
res_str += f" {iterator.data} |"
iterator = iterator.next # 다음 노드로 넘어간다.
return res_str
👉링크드 리스트 ★접근 연산★
- 배열과 같이 인덱스로 링크드 리스트에 접근이 가능하다.
- 단, 특정 위치에 있는 노드를 리턴하는 연산!
- 배열은 주소로 바로 값에 접근이 가능하지만, 레퍼런스로 접근
def find_node_at(self, index):
"""링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
iterator = self.head
for _ in range(index):
iterator = iterator.next
return iterator
👉링크드 리스트 접근 시간 복잡도
- 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 가면 됨!
- 마지막 노드에 접근하려면 head 에서 다음 노드로 n -1 번 가야 됨
👉 링크드 리스트 ★탐색 연산★
# 탐색연산
def find_node_with_data(self, data):
"""링크드 리스트에서 탐색 연산 메소드. 단, 해당 노드가 없으면 None을 리턴한다"""
# 코드를 쓰세요
iterator = self.head # nod
while iterator.data != data:
iterator = iterator.next
if iterator is None:
return None
return iterator
👉 링크드 리스트 ★삽입 연산★
def insert_after(self, previous_node, data):
"""링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
new_node = Node(data)
# tail 노드 다음에 노드를 삽입할 때
if previous_node is self.tail:
self.tail.next = new_node
self.tail = new_node
else: # 두 노드 사이에 삽입할 때
new_node.next = previous_node.next
previous_node.next = new_node
👉 링크드 리스트 가장 앞 삽입
내가 푼 결과랑 정답과 똑같아서 행복하다.
def prepend(self, data):
"""링크드 리스트의 가장 앞에 데이터 삽입"""
# 코드를 쓰세요
# 노드를 생성
new_node = Node(data)
# 링크드 리스트가 비어있으면
if self.head is None:
self.head = new_node
self.tail = new_node
else: # 링크드 리스트가 비어있지 않으면
new_node.next = self.head
self.head = new_node
👉 링크드 리스트 삭제
def pop_left(self):
"""링크드 리스트의 가장 앞 노드 삭제 메소드. 단, 링크드 리스트에 항상 노드가 있다고 가정한다"""
# 코드를 쓰세요
# 가장 앞 노드 데이터
data = self.head.data
if self.head is self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
return data
더블 링크드 리스트
- 싱글리 링크드 리스트에서 안 바꿔도 되는 메소드
- find_node_at(접근 연산)
- find_node_with_data(탐색 연산)
- __str__ 메소드
👉 더블 링크드 리스트 ★삽입 연산★
def insert_after(self, previous_node, data):
"""링크드 리스트 추가 연산 메소드"""
# 코드를 쓰세요
# 새로운 노드로
new_node = Node(data)
# tail 노드 다음에 노드를 삽입할 때
if previous_node is self.tail:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
else:
# 새롭게 생성한 노드를 이미 있는 링크드 리스트에 연결시키고
new_node.prev = previous_node
new_node.next = previous_node.next
# 이미 있는 노드들의 앞과 다음 레퍼런스를 새롭게 생성한 노드로 지정한다
previous_node.next.prev = new_node
previous_node.next = new_node