연결리스트
데이터를 감싼 노드를 포인터로 연결해서 공간적 효율성을 극대화시킨 자료구조.
삽입, 삭제 : O(1)
탐색 : O(n)
그림처럼 prev포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결리스트이며, 연결리스트는 싱글연결리스트, 이중연결리스트, 원형 이중연결리스트가 있다.
head : 맨 앞에있는 노드
next, prev 라는 포인터가 다음 노드의 메모리 주소를 저장하고 있기 때문에 이 포인터를 사용하여 다음 노드로 이동이 가능하다.
연결리스트는 배열보다 삽입,삭제가 용이하다
-> 연결리스트는 중간에 요소를 찾는 과정이 필요 없고, 단순히 포인터를 변경하는 것만으로도 수행할 수 있기 때문.
ex) 1,2,3,4,5 의 숫자를 담고있는 배열or연결리스트로 데이터를 관리하는 상황(삽입,삭제)
1. 배열을 쓰면?
요소를 추가, 삭제할 때 요소의 인덱스를 알아야한다. 요소를 추가하려면 추가할 위치 이후의 모든 요소를 뒤로 한칸씩 이동시켜야함.(시간 복잡도 상승. 삭제도 마찬가지)
2. 연결리스트를 쓰면?
요소를 추가하거나, 삭제할 때 해당 요소를 가리키는 포인터만 변경하면 됨.
새로운 요소를 추가할 때는 새로운 요소의 다음 노드를 현재 노드의 다음노드로 설정하고, 현재 노드의 다음 노드를 새로운 요소로 설정하면 된다.(포인터 변경만 하면 되므로 시간복잡도 낮음)
연결리스트 종류 설명
- 싱글 연결 리스트 : next 포인터만 가진다.
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
이중 연결리스트 파이썬 예시
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
#이중 연결 리스트 생성
dll = DoublyLinkedList()
#노드 추가
dll.append(1)
dll.append(2)
dll.append(3)
#리스트 출력
dll.print_list()
# 결과 : 1 -> 2 -> 3 -> None 배열(array)
array. 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
중복허용o 순서o
여기서의 배열은 '정적 배열'을 기반으로 설명한다.
접근(참조) : O(1). 랜덤접근 가능
삽입과 삭제 : O(n)
따라서 데이터 추가와 삭제를 많이 하는 것은 연결리스트, 접근(참조)를 많이 하는 것은 배열로 하는 것이 좋다.
랜덤 접근과 순차적 접근
직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다(인덱스 써서 직접 접근하는걸 말함). 이는 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대이다.
ex) 배열을 사용하여 리스트, 스택, 큐 등을 구현할 때 랜덤접근을 통해(인덱스) 요소에 빠르게 접근할 수 있어서 데이터를 효율적으로 다룰 수 있다.
배열과 연결리스트 비교
배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.
연결리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다.
그림에서 유추할 수 있듯이 n번째 요소의 접근은 배열은 빠르고 연결리스트는 느리다.
배열의 경우 그저 상자 위에 있는 요소를 접근하면 되기 때문에 O(1)의 시간 복잡도를 가지고, 연결 리스트는 매번 상자를 열어야하고 주어진 선을 기반으로 순차적으로 열어야 하기 때문에 접근의 경우 O(n)의 시간 복잡도를 가진다. 즉, 참조가 많이 일어나는 작업의 경우 배열이 빠르고 연결리스트는 느리다.
하지만 데이터 추가, 삭제는 연결리스트가 더 빠르고 배열은 느리다.
배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결리스트는 선을 바꿔서 연결해주기만 하면 되기 때문.
벡터
벡터는 동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에 개수를 모른다면 벡터를 써야 한다. 또한, 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
탐색, 맨 뒤 요소 삭제, 삽입 : O(1)
맨 뒤가 아닌 요소 삭제, 삽입 : O(n)
뒤에서부터 삽입하는 push_back() 의 경우 O(1)의 시간이 걸리는데, 벡터의 크기가 증가되는 시간 복잡도가 amortized 복잡도, 즉 상수 시간 복잡도 O(1)과 유사한 시간복잡도를 가지기 때문.
그림처럼 push_back()을 한다고 해서 매번 크기가 증가하는 것이 아니라 2^n + 1 마다 크기를 2배로 늘리는 것을 알 수 있다.
c_i 를 i번째 push_back()을 할 때 드는 비용이라고 한다면,
c_i = 1 or c_i = 1 + 2^k 이다
그렇다면 n번 push_back()을 한다고 했을 때 드는 비용 T(n)은
이를 n으로 나누게 되면 push_back() 을 할 때 평균적으로 드는 비용을 알 수 있는데 이것이 3이기 때문에 이는 1이라는 상수 시간 보다는 크지만 상수 시간에 가까운 amortized 복잡도를 가진다는걸 알 수 있다.
그렇기 때문에 push_back()은 O(1)의 시간복잡도를 가진다고 할 수 있다.
파이썬의 리스트 = 벡터
파이썬의 리스트는 동적배열로 구현되어 있어 벡터와 유사한 동작을 한다. 파이썬의 리스트는 요소를 추가하거나 삭제할 떄 메모리를 효율적으로 관리하며 인덱스를 통한 임의 접근도 빠르게 처리한다. 이러한 특성 때문에 파이썬의 리스트는 다양한 상황에서 사용되며, 대부분의 경우 벡터의 역할을 충분히 수행할 수 있다.
동적배열?
-> 크기를 동적으로 조절할 수 있는 배열을 말함.
예를들어 파이썬의 리스트 크기를 늘리는 작업을 한다고 가정해보자.
-
새로운 리스트 할당 : 먼저 새로운 배열을 할당하기 위해 메모리에서 추가 공간을 확보한다. 이를 위해 운영체제는 프로그램에게 메모리를 할당하는 시스템 호출을 수행하고, 프로그램은 할당된 메모리를 사용 할 수 있게 된다.
-
기존 배열 요소 복사 : 이전 배열에 있는 모든 요소를 새로운 배열로 복사한다. 이 과정은 기존 배열의 요소를 하나씩 새 배열에 복사하여 이루어진다. 보통 반복문이 사용되며, 요소를 순회하며 복사하게된다.
-
기존 배열 해제 : 새로운 배열로 모든 요소를 복사한 후에는 이전 배열을 해제한다. 이는 프로그램이 더 이상 기존 배열을 사용하지 않으므로 할당된 메모리를 운영체제에 반환하여 다른 용도로 사용할 수 있게 한다.
이러한 과정들은 동적 배열이 요소를 추가할 때 마다 수행된다. 배열의 크기를 늘리는 작업은 새로운 배열을 할당하고 기존 배열의 요소를 복사하여 새 배열을 옮기는 작업을 포함하므로, 메모리 할당 및 복사 작업이 필요하다.
이러한 작업은 프로그램 성능에 영향을 미치므로 배열의 크기를 조절할 때 이러한 작업을 최소화 하는것이 중요하다.
