📌 링크드 리스트란
추상 데이터 타입의 리스트를 구현한 자료구조이다.
순서가 있는 값을 저장하지만 링크드리스트에는 인덱스가 없다.
링크드 리스트의 구조
링크드 리스트는 순서가 있는 자료구조이지만 연속적인 메모리 블록에 저장되지 않는다.
그 대신 링크드 리스트는 노드로 이루어져있다.
노드 = 필드 + 포인터- 필드: 데이터를 보관
- 포인터: 다음 노드의 위치를 저장
- 헤드 : 첫번째 노드
- 테일 : 마지막 노드
링크드 리스트의 종류
단일 링크드 리스트
- 후에 올 노드의 주소를 가리키는 포인터만 존재한다.
이중 링크드 리스트
- 다음 요소를 가리키는 포인터와 이전 요소를 가리키는 포인터가 있다.
따라서 두 방향의 포인터를 통해 어느 방향으로든 이동할 수 있다.
환형 링크드 리스트
- 마지막 노드에 첫 번재 노드를 기리키는 포인터가 있어서 처음으로 돌아올 수 있다.
따라서 반복적으로 순환할 수 있다. - 이런 경우 이 리스트에 사이클이 있다 라고 표현한다.
링크드 리스트의 성능
데이터가 평균일 때
| 접근 | 탐색 | 삽입 | 삭제 | |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(1) |
| 링크드 리스트 | O(n) | O(n) | O(1) | O(1) |
배열 접근이 O(1)인 이유
인덱스를 알고 있으면 바로 접근이 가능하다.
링크드 리스트 접근이 O(n)인 이유
노드로 연결되어 있는 리스트를 선형 탐색해야만 원하는 요소에 접근할 수 있기 때문이다.
⭐ 링크드 리스트 삽입이 O(1)인 이유
한 노드를 삽입하려고 할 때, 앞선 노드의 포인터 값을 추가하려는 노드의 주소값으로 변경하고, 삽입하려고하는 노드의 포인터를 이후 노드의 주소로 추가하면 된다.
따라서 메모리 할당이나 추가적인 작업이 필요하지 않다.
👉 링크드 리스트의 장점
링크드 리스트의 단점
포인터를 저장하기 위한 추가적인 메모리 공간이 필요하다.
임의 접근이 힘들다.
인덱스 값이 없기 때문에, 무조건 포인터를 따라 움직여야한다.
파이썬에서 링크드 리스트 만들기
왜 자료구조를 C언어로 듣는지 알 것 같다..ㅎ링크드 리스트를 만들고 값 추가
class Node:
def __init__(self,data,next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self,data):
if not self.head:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)이 링크드 리스트는 맨 뒤에 추가하도록 했다.
따라서 current가 맨 마지막일 때까지 반복문을 돌리고,
current.next에 해당 값을 추가하도록 했다.
출력 메서드 만들기
def __str__(self):
re = ""
node = self.head
while node is not None:
re += str(node.data) +" "
node = node.next
return re교재에서는 직접 print를 하도록 되어있는데, 파이썬에서 __str__는 기본적으로 문자열을 반환하는 것으로 되어있다.
따라서 문자열을 반환하도록 수정하였다.
링크드 리스트의 탐색
def serch(self,target):
current = self.head
if current is None:
return False
while current is not None:
if current.data == target:
return True
current = current.next
return False아주 간단했다 👍
링크드 리스트 해당 값 모두 제거하기
def removeAll(self,target):
while self.head.data is target:
self.head = self.head.next
currnet = self.head.next
pre = self.head
while currnet:
if currnet.data == target:
pre.next = currnet.next
else:
pre = currnet
currnet = currnet.next
만약 현재 노드의 데이터 값이 삭제하고자 하는 값이었다면 제거한다.
이때 제거 하고 나서는 이전 노드를 의미하는 pre를 현재 노드로 업데이트 해주면 안된다.
링크드 리스트 뒤집기
def reverse_list(self):
current = self.head
previous = None
while current: #지금
next = current.next
current.next = previous
previous = current
current = next
self.head = previous맨 처음의 next에 None을 넣어야하는게 까다로웠다.
환형 리스트 만들기
class LinkedListCycle:
def __init__(self):
self.head = None
def append(self,data):
if not self.head:
self.head = Node(data)
self.head.next = self.head
return
current = self.head
while current.next != self.head:
current = current.next
current.next = Node(data)
current = current.next
current.next = self.head
def __str__(self):
re = ""
node = self.head
if node is not None:
re += str(node.data) +" "
node = node.next
while node is not self.head:
re += str(node.data) +" "
node = node.next
return re
def serch(self,target):
current = self.head
if current is None:
return False
if current.data == target:
return True
current = current.next
while current is not self.head:
if current.data == target:
return True
current = current.next
return False
def removeAll(self,target):
while self.head.data is target:
if self.head.next == self.head:
self.head = None
return
else:
self.head = self.head.next
currnet = self.head.next
pre = self.head
while currnet != self.head:
if currnet.data == target:
pre.next = currnet.next
else:
pre = currnet
currnet = currnet.next
def detect_cycle(self):
slow = self.head
fast = self.head
while True:
try:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
except:
return False링크드 리스트의 사이클 찾기
def detect_cycle(self):
slow = self.head
fast = self.head
while True:
try:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
except:
return False사이클이 있다면 언젠가는 동일해진다.
