1. 연결 리스트(Linked list)
대표적인 선형 자료 구조
다양한 추상 자료형(ADT) 구현의 기반이 된다.
각 요소들이 참조로 이어져 있으며 각 요소는 노드로 이루어져 있다.
노드 = 데이터를 담는 부분 + 다음 노드를 가르키는 참조형태로 구성
-
단순 연결 리스트: 다음 노드를 가리키는 참조 하나만 가짐
-
이중 연결 리스트: 앞 노드를 가리키는 참조, 뒤 노드를 가리키는 참조를 모두 가짐
1-1. 연결 리스트의 사용
-
삽입과 삭제가 빈번한 경우에 사용을 고려할 수 있음
-
사용 예시
-
OS에서 힙 메모리를 할당, 해제할 때 이중 연결 리스트로 구현하는 경우
-
트리 구현하는 경우
-
2. 연결 리스트의 연산
2-1. 삽입
두 노드 사이에 새로운 노드를 삽입하는 과정.
아래 그림과 같이 앞 뒤 노드의 link를 변경해주는 방식.
참조 할당 연산 2회만 필요로 하기 때문에 빅오는O(1)이다.
이미지 출처: http://arkainoh.blogspot.com/2018/06/array.linkedlist.html
2-2. 삭제
기존 노드를 삭제할 때는 삭제하고자 하는 노드와 연결되어 있는 노드의 참조를 변경해준다.
참조 할당 연산 1회만 필요하여 빅오는 역시O(1)이다.
-
삭제된 노드는 가비지 컬렉션으로 인해 메모리에서 사라짐
-
파이썬은 레퍼런스 카운트로 가비지 컬렉션 지원
-
가비지 컬렉션: 언어 차원에서 메모리를 관리해주는 것
-
레퍼런스 카운트: 어떤 객체를 가리키는 객체 개수가 0이 될 때 해당 객체를 지우는 것
-
이미지 출처: http://arkainoh.blogspot.com/2018/06/array.linkedlist.html
2-3. 탐색
연결 리스트는 인덱싱 불가
리스트의 처음부터 끝까지 하나씩 방문하여 요소 탐색
데이터의 개수가 n개라면 최악의 경우 n번 탐색 →O(n)
3. 동적 배열과 연결 리스트
동적 배열과 연결 리스트는 정반대의 특징을 가지기 때문에 상황에 맞게 선택하여야 한다.
| 동적 배열 | 연결 리스트 | |
|---|---|---|
| 삽입 및 삭제 | O(n) | O(1) |
| 탐색 | O(1) | O(n) |
4. 더미 이중 연결 리스트(dummy double linked list)
4-1. 노드 생성
-
__data: 데이터 저장 -
__prev: 이전 노드 참조 -
__next: 다음 노드 참조 -
@property: 외부에서__data,__prev,__next에 접근할 때 실제 변수 이름대신data,prev,next로 접근할 수 있게 함
class Node:
def __init__(self, data=None):
self.__data = data
self.__prev = None
self.__next = None
# 소멸자: 객체가 사라지기 전 호출 (확인을 위함)
def __del__(self):
print("data of {} is deleted".format(self.data))
@property
def data(self):
return self.__data
@data.setter
def data(self, data):
self.__data = data
@property
def prev(self):
return self.__prev
@prev.setter
def prev(self, p):
self.__prev = p
@property
def next(self):
return self.__next
@next.setter
def next(self, n):
self.__next = n
4-2. 이중 연결 리스트 클래스 구현
- 리스트의 맨 처음과 끝은 실제 데이터를 저장하지 않으며, 이를 더미 노드라고 함
class DoubleLinkedList:
def __init__(self):
self.head = Node()
self.tail = Node()
# head와 tail 연결
self.head.next = self.tail
self.tail.prev = self.head
# 데이터 개수를 저장하는 변수
self.d_size = 0
4-3. operation 구현
-
상태 확인
-
empty(): 비어있으면 True 아니면 False -
size(): 요소 개수 반환
-
# empty
def empty(self):
if self.d_size == 0:
return Ture
else:
return False
# size
def size(self):
return self.d_size
-
새로운 노드 삽입
-
add_first: 리스트 맨 앞에 data 추가 -
add_last: 리스트 맨 마지막에 data 추가 -
insert_after: data를 다음 노드에 삽입 -
insert_before: data를 이전 노드에 삽입
-
# add_first
# 노드 참조 순서를 지켜줘야 함 (주의)
def add_first(self, data):
new_node = Node(data)
new_node.next = self.head.next
new_node.prev = self.head
self.head.next.prev = new_node
self.head.next = new_node
self.d_size += 1
# add_last
def add_last(self, data):
new_node = Node(data)
new_node.prev = self.tail.prev
new_node.next = self.tail
self.tail.prev.next = new_node
self.tail.prev = new_node
self.d_size += 1
# insert_after
def insert_after(self, data, node):
new_node = Node(data)
new_node.next = node.next
new_node.prev = node
node.next.prev = new_node
node.next = new_node
self.d_size += 1
# insert_before
def insert_before(self, data, node):
new_node = Node(data)
new_node.prev = node.prev
new_node.next = node
node.prev.next = new_node
node.prev = new_node
self.d_size += 1
-
요소 탐색
-
search_forward(target): target을 리스트 처음부터 찾아가며 노드 반환 -
search_backward(target): target을 리스트 마지막부터 찾아가며 노드 반환
-
# search_forward
def search_forward(target):
cur = self.head.next # 첫번째 데이터 노드
while cur is not self.tail:
if cur.data == target:
return cur
cur = cur.next
return None
# search_backward
cur = self.tail.prev # 마지막 데이터 노드
while cur is not self.head:
if cur.data == target:
return cur
cur = cur.prev
return None
-
삭제 연산
-
delete_first: 리스트의 첫 번째 데이터 노드 삭제 -
delete_last: 리스트의 마지막 데이터 노드 -
delete_node: 노드 삭제
-
# delete_first
def delete_first(self):
if self.empty():
return
self.head.next = self.head.next.next
self.head.next.prev = self.head
self.d_size -= 1
# delete_last
def delete_last(self):
if self.empty():
return
self.tail.prev = self.tail.prev.prev
self.tail.prev.next = self.tail
self.d_size -= 1
# delete_node
def delete_node(self, node):
if self.empty():
return
node.prev.next = node.next
node.next.prev = node.prev
self.d_size -= 1
