🥪Array & Linked List

1. Array

🥪 Array(배열)는 메모리 상에 원소를 연속하게 배치한 자료구조를 뜻한다. O(1)에 k번째 원소를 확인/변경 가능하다. 또한 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(overhead)가 거의 없으며, 메모리 상에 데이터들이 붙어 있어서 cache hit rate가 높다. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. 

 

※ array에서의 cache hit rate가 높은 이유?

: 데이터가 연속해서 배치되어 있으므로 cache 입장에서 array 내의 인근 데이터까지 cache block에 load 하므로 임의의 array 내의 원소 접근 시 인근 원소 역시 cache에 있을 확률이 높다. 그리고 반복적으로 동일한 array 내의 원소를 접근한다면 cache 내에 해당 원소가 있을 확률이 높다. 따라서 spatial locality와 temporal locality 두 가지 성질을 모두 활용한 이점으로 cache hit rate가 커질 확률이 높으며 좋은 프로그램 성능 향상으로 이어짐

 

🥪 임의의 위치에 있는 원소를 확인/변경에는 O(1)의 시간 복잡도, 원소를 끝에 추가하는 연산도 O(1), 마지막 원소를 제거하는 연산도 O(1), 임의의 위치에 원소를 추가하는 연산은 O(N) (중간에 원소를 넣기 위해 이후의 원소들을 모두 밀어야 하기 때문), 임의의 위치에 원소를 제거하는 연산도 O(N) (중간 원소 제거한다면 array의 정의에 의해 빈 공간이 남지 않게끔 밀어야 하기 때문)

 

🥪 python) 원소 확인/변경은 arr[x], arr[x] = y / 원소 끝에 추가하는 연산은 append() 함수 활용 / 마지막 원소 제거는 del arr[-1] / 임의의 위치에 원소 추가는 insert() 함수 활용/ 임의의 위치에 원소 제거는 del arr[x] 활용

2. Linked List

🥪 linked list(연결 리스트)는 원소들을 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조이다. 즉 원소는 아래와 같이 연속적으로 저장되어 있지 않고 이곳저곳 흩어져 있다. 이 때 맨 앞의 데이터를 안다면 연속적으로 이어진 모든 데이터를 가져올 수 있다. 

🥪 k번째 원소를 확인/변경하기 위해 O(k) 필요(예를 들어 세 번째 원소를 찾기 위해서는 첫 번째 원소부터 세 번째 원소까지 이동해야 함) / 임의의 위치에 원소를 추가/ 임의의 위치의 원소 제거는 O(1)이다. 또한 원소들이 메모리 상에 연속해 있지 않아 cache hit rate가 낮지만 할당이 다소 쉽다.  

 

🥪 연결리스트에는 각 원소가 자신의 다음 원소의 주소를 들고 있는 단일 연결 리스트(singly linked list). 각 원소가 이전 원소와 다음 원소의 주소를 둘 다 들고 있는 이중 연결 리스트(doubly linked list) - 따라서 이전 원소의 정보를 알 수 있는 장점이 있지만 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 쓴다는 단점 존재. 끝이 처음과 연결되어 있는 원형 연결 리스트(circular linked list) (각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관 x)

(위 부터) 단일 연결 리스트 - 이중 연결 리스트 - 원형 연결 리스트

🥪  배열과 연결 리스트 모두 원소들 간에 선후 관계 일대일로 정의. 따라서 두 자료구조 모두 선형 자료 구조

	array	linked list
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	(위치의 주소를 안다면) O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(overhead)	-	O(N)

 

🥪 임의의 위치에 있는 원소를 확인/변경하는 데는 O(N)의 시간 복잡도: 임의의 위치까지 가는데 순차적으로 원소 순서대로 이동해야 함. 첫번째 원소의 주소만 알고 있으므로 k번째 원소까지 이동하는데 k번 이동 / 임의의 위치에 원소를 추가하는 데는 O(1)의 시간 복잡도. 예를 들어 21과 17 사이에 84를 넣고 싶을 때 17부터 뒤의 원소를 모두 이동시킬 필요 없이 그저 21과 84에서 다음 원소의 주소만 변경을 해주면 간단하게 끝나기 때문. (다만, 추가하고자 하는 원소의 주소를 알 경우만 O(1). 추가하고자 하는 원소의 내용만 안다면 삽입하고자 하는 위치까지 이동해야 하므로 O(N)) / 임의 위치에 원소 제거는 O(1). 예를 들어 65 - 21 - 17이 연결되어 있을 때, 21 원소를 제거하고 싶다면 65 다음의 주소가 17로 되어있게끔 연결만 해주면 됨 (이후 21은 메모리 누수 방지를 위해 추가 작업이 필요하지만)   

 

🥪 예를 들어 커서가 가리키는 위치에 글자를 추가하거나 지우는 명령을 수행하는(O(1) 가능) 텍스트 에디터에 효율적. 즉 임의의 위치에 원소를 추가하거나 제거하는 경우 연결 리스트를 고려하면 좋다. 

---

BaaarkingDog

geeksforgeeks