2. Linked List
1. Linked List
리스트는 데이터에 순서를 매겨 늘어놓은 자료구조이다. 기본적인 리스트는 모든 원소를 연속으로 메모리에 배치한다. 하지만 연결리스트는 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는 자료구조다. 즉, 메모리를 연속적으로 사용하지 않는다. 실제로 컴퓨터의 물리 메모리에는 서로 연결된 형태로 구성되어 있으며 메모리 어딘가에 여기저기 흩뿌려져있다. 다음은 연결리스트의 기본적이 구조이다.
연결 리스트에서 각각의 원소를 노드라고 한다. 노드가 갖고 있는 것은 데이터와 다음 노드를 가리키는 포인터이다. 맨 앞의 노드를 머리노드, 맨 뒤에 있는 노드를 꼬리 노드라고 한다.
2. Array vs Linked List
배열과 연결리스트가 가지는 시간복잡도를 살펴보자.
데이터 탐색
- 배열: O(1)
- 연결리스트: O(N)
연결리스트는 배열과 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수 시간에 접근할 수 없다. 즉, 탐색에는 O(N)의 시간이 걸린다.
반면 배열은 인덱스 번호를 통해서 탐색하기 때문에 O(1)의 시간이 걸린다.
데이터 추가
먼저 데이터를 추가하는 행위 자체의 시간복잡도는 O(1)이다. 메모리 주소 값만 노드에 할당하면 되기 때문이다.
- 배열: 최소 O(1), 최대 O(N)
- 연결리스트: 최소 O(1), 최대 O(N)
연결리스트에 추가하려는 데이터의 위치가 맨 앞이라면 O(1) 시간안에 가능하다. 하지만 추가하려는 데이터의 위치가 맨 처음이 아니라면 맨 앞 노드부터 순차적으로 탐색하면서 그 위치까지 가야한다. 따라서 O(N)의 시간복잡도를 가진다.
배열은 데이터들이 메모리상에 순차적으로 저장되어 있다. 따라서 중간에 데이터를 추가할 경우 그 뒤에 있는 데이터들을 전부 한 칸씩 뒤로 밀면서 메모리 할당을 조정해야 한다 O(N). 하지만 맨 뒤에 데이터를 추가할 때는 O(1)안에 실행할 수 있다.
데이터 삭제
데이터 삭제는 데이터 추가하는 경우와 같다.
- 배열: 최소 O(1), 최대 O(N)
- 연결리스트: 최소 O(1), 최대 O(N)
연결리스트에서 맨 앞의 데이터를 삭제한다면 O(1), 그 뒤의 데이터를 삭제한다면 맨 앞 노드부터 순차적으로 탐색해야 하기 때문에 O(N)이다.
배열에서 맨 뒤의 데이터를 삭제한다면 O(1), 중간의 데이터를 삭제한다면 그 뒤의 데이터들은 한칸씩 앞으로 옮겨줘야 하기 때문에 O(N)이다.
정리하면 배열은 연속적인 메모리를 할당받아서 데이터를 저장하기 때문에 탐색은 굉장히 빠르다. 반면에 연결리스트는 노드가 있기 때문에 데이터의 추가/삭제가 간편하지만 탐색이 느려졌다. 따라서 데이터의 탐색이 중요하면 배열, 데이터의 추가/삭제가 중요하다면 연결리스트를 사용하는 것이 좋다.
3. Linked List with Python
이번에는 연결리스트를 파이썬으로 구현해본다.
# 노드 정의
class Node:
def __init__(self, data, next):
self.data = data
self.next = None
# LinkedList 정의
class LinkedList:
# 초기화: 노드가 하나도 없는 빈 연결 리스트 생성
# 노드가 존재하지 않는 빈 연결 리스트는 head가 참조하는 곳이 없으므로 그 값을 None으로 함
def __init__(self):
self.no = 0 # 리스트에 존재하는 노드의 개수
self.head = None # 머리 노드를 참조하기 위한 head(head는 머리 노드에 대한 참조일 뿐 머리노드 그 자체가 아님)
self.current = None # 현재 노드
# 연결 리스트의 노드 개수를 반환하는 함수
def __len__(self):
return self.no
# 검색을 수행하는 함수
def search(self, data):
# data와 값이 같은 노드를 탐색
cnt = 0 # 맨 앞에서 몇 번째 원소를 스캔하고 있는지를 나타낸 변수를 0으로 초기화
ptr = self.head # 현재 스캔 중인 노드를 참조하기 위한 변수: 처음에는 머리 노드 A를 참조하고 있음
# ptr이 None이 아니면. 즉, 더 스캔할 노드가 존재하지 않으면 while 문 종료
while ptr is not None:
# 스캔중인 현재 노드의 값이 data와 같으면 찾은 노드 위치 반환
if ptr.data == data:
self.current = ptr
return cnt
# 다르면 다음 노드로 스캔을 진행
cnt += 1
ptr = ptr.next
# 찾고자 하는 값이 없으면 -1 반환
return -1
# 리스트에 data와 값이 같은 노드가 존재하는지 판단하는 함수
def __contains__(self,data):
return self.search(data) >= 0
# 리스트의 맨 앞에 노드를 삽입하는 함수
def add_first(self, data):
ptr = self.head # 삽입하기 전 머리 노드 A를 참조하는 포인터를 ptr에 저장
self.head = self.current = Node(data, ptr) # 새로운 노드의 데이터는 data가 되고 뒤쪽 포인터가 참조하는 곳은 ptr(삽입하기 전의 머리 노드 A)
self.no += 1
# 리스트의 맨 뒤에 노드를 삽입하는 함수
def add_last(self, data):
# 리스트가 비어있으면 맨 앞에 노드를 삽입
if self.head is None:
self.add_first(data)
else:
# 맨 앞쪽 노드부터 꼬리 노드를 찾는 과정 수행
ptr = self.head
while ptr.next is not None:
ptr = ptr.next
# 삽입전 마지막 노드가 삽입된 노트를 참조하도롤 업데이트
ptr.next = self.current = Node(data,None) # 마지막은 링크가 None임
self.no += 1
# 머리 노드를 삭제하는 함수
def remove_first(self):
# 리스트가 비어있지 않으면 삭제 진행
if self.head is not None:
# head는 삭제하기 전 머리 노드가 참조했던 노드를 참조하도록 함
self.head = self.current = self.head.next
self.no -= 1
# 마지막 노드를 삭제하는 함수
def remove_last(self):
# 노드가 한 개 이상 일때
if self.head is not None:
# 노드가 한개 일때
if self.head.next is None:
self.remove_first()
# 노드가 두개 이상일때
else:
ptr = self.head # 스캔중인 노드
pre = self.head # 스캔중인 노드 바로 앞 노드
# 마지막 노드 찾기
while ptr.next is not None:
pre = ptr
ptr = ptr.next
pre.next = None
self.current = pre
self.no -= 1
# 임의의 노드 p를 삭제하는 함수
def remove(self, p):
# 리스트가 비어있지 않을 때
if self.head is no None:
# p가 머리노드이면 머리 노드를 삭제
if p is self.head:
self.remove_first()
# 아니면 p의 위치 찾아서 삭제
else:
ptr = self.head # 처음 노드 부터 살펴보기
while ptr.next is not p:
ptr = ptr.next
if ptr is None:
return
# p가 가리키는 다음노드를 현재 스캔중인 노드의 다음 노드로 연결
ptr.next = p.next
self.current = ptr
self.no -= 1
# 현재 스캔 중인 노드를 삭제
def remove_current_node(self):
self.remove(self.current)
# 전체 노드를 삭제
def clear(self):
# 전체가 빌 때까지 머리 노드를 삭제
while self.head is not None:
self.remove_first()
self.current = None
self.no = 0
# 현재노드를 한 칸 뒤로 이동시키는 함수 (뒤쪽 노드가 존재해야 함)
def next(self):
if self.current is None or self.current.next is None:
return False
self.current = self.current.next
return True
# 현재노드를 출력하는 함수
def print_current_node(self):
if self.current is None:
print('노드가 존재하지 않음')
else:
print(self.current.data)
# 모든 노드를 출력
def print(self):
ptr = self.head
while ptr is not None:
print(ptr.data)
ptr = ptr.next
4. Doubly Linked List (Bidirectional Linked List)
연결 리스트의 단점은 뒤쪽 노드를 찾기는 쉽지만 앞쪽 노드를 찾기 어련다는 것이다. 이 단점을 개선한 리스트 구조가 이중 연결 리스트이다. 이중 연결 리스트는 아래 그림처럼 앞쪽 노드와 뒤쪽 노드에 대한 포인터가 모두 주어진다.
5. Circular Linked List
원형 리스트는 꼬리 노드가 다시 머리 노드를 가리키는 모양을 하고 있다. 연결 리스트와는 다르세 꼬리 노드의 뒤쪽 포인터가 None이 아니라 머리 노드의 포인터값이 된다는 것이다.
6. Circular Doubly Linked List
원형 이중 연결 리스트는 원형 리스트와 이중 연결 리스트를 결합한 것이다.
Circular Doubly Linked List with Python
"""원형 이중 연결 리스트용 노드 클래스"""
class Node:
def __init__(self, data, prev, next):
"""초기화"""
self.data = data # 데이터
self.prev = prev or self # 앞쪽 포인터: prev가 None이 아니면 prev대입, None이면 self를 대입
self.next = next or self # 뒤쪽 포인터: next가 None이 아니면 prev대입, None이면 self를 대입
"""원형 이중 연결 리스트 클래스"""
class DoubleLinkedList:
"""초기화"""
# 비어있는 원형 이중 연결 리스트 생성
# 데이터가 없는 노드 (삽입과 삭제를 용이하게 하는 리스트의 맨 앞에 존재하는 더미 노드) 1개 만들기
def __init__(self):
self.head = self.current = Node() # 더미 노드를 생성
self.no = 0
"""선형 리스트의 노드 수를 반환"""
def __len__(self):
return self.no
"""리스트가 비어 있는가?"""
def is_empty(self):
# 더미노드만 존재하는 검사
# 더미 노드의 두쪽 포인터 head.next가 더미 노드인 head를 참조하면 비어있는것임
return self.head.next is self.head
"""data와 값이 같은 노드를 검색"""
def search(self, data):
cnt = 0
# 첫번째 노드 부터 스캔
ptr = self.head.next # 현재 스캔 중인 노드
# 다시 처음으로 돌아오기 전까지 진행
while ptr is not self.head:
if data == ptr.data:
self.current = ptr
return cnt # 검색 성공
cnt += 1
ptr = ptr.next # 뒤쪽 노드에 주목
return -1 # 검색 실패
"""연결 리스트에 data가 포함되어 있는가?"""
def __contains__(self, data):
return self.search(data) >= 0
"""주목 노드를 출력"""
def print_current_node(self):
if self.is_empty():
print('주목 노드는 없습니다.')
else:
print(self.current.data)
"""모든 노드를 출력"""
def print(self):
ptr = self.head.next # 더미 노드의 뒤쪽 노드
while ptr is not self.head:
print(ptr.data)
ptr = ptr.next # 다음 노드로 넘기기
"""모든 노드를 역순으로 출력"""
def print_reverse(self):
ptr = self.head.prev # 더미 노드의 앞쪽 노드 (가장 뒤쪽 노드)
while ptr is not self.head:
print(ptr.data)
ptr = ptr.prev
"""주목 노드를 한 칸 뒤로 이동"""
def next(self):
if self.is_empty() or self.current.next is self.head:
return False # 이동할 수 없음
self.current = self.current.next
return True
"""주목 노드를 한 칸 앞으로 이동"""
def prev(self):
if self.is_empty() or self.current.prev is self.head:
return False # 이동할 수 없음
self.current = self.current.prev
return True
"""주목 노드의 바로 뒤에 노드를 삽입"""
def add(self, data):
node = Node(data, self.current, self.current.next)
self.current.next.prev = node
self.current.next = node
self.current = node
self.no += 1
"""맨 앞에 노드를 삽입"""
def add_first(self, data):
self.current = self.head # 더미 노드 head의 바로 뒤에 삽입
self.add(data)
"""맨 뒤에 노드를 삽입"""
def add_last(self, data):
self.current = self.head.prev # 꼬리 노드 head.prev의 바로 뒤에 삽입
self.add(data)
"""주목 노드 삭제"""
def remove_current_node(self):
if not self.is_empty():
self.current.prev.next = self.current.next
self.current.next.prev = self.current.prev
self.current = self.current.prev
self.no -= 1
if self.current is self.head:
self.current = self.head.next
"""노드 p를 삭제"""
def remove(self, p):
ptr = self.head.next
while ptr is not self.head:
if ptr is p: # p를 발견
self.current = p
self.remove_current_node()
break
ptr = ptr.next
"""머리 노드 삭제"""
def remove_first(self):
self.current = self.head.next # 머리 노드 head.next를 삭제
self.remove_current_node()
"""꼬리 노드 삭제"""
def remove_last(self):
self.current = self.head.prev # 꼬리 노드 head.prev를 삭제
self.remove_current_node()
"""모든 노드를 삭제"""
def clear(self):
while not self.is_empty(): # 리스트 전체가 빌 때까지
self.remove_first() # 머리 노드를 삭제
self.no = 0