자료 구조를 공부하고 나서, Linked List와 Array가 서로 비슷하게 느껴졌다.
GeeksforGeeks에 비교해 놓은 글이 있어서 번역해 둔다.
(다시 읽으려면 힘드니까.....ㅎㅎㅎㅎㅎㅎ)
참고로 '기울기'로 표현한 부분은 추가로 공부하고 작성한 부분이다.
원글 : GeeksforGeeks - Linked List vs Array
Array와 Linked List 모두 유사한 유형의 선형데이터* 를 저장하는데 사용된다.
그러나 Array, Linked List 모두 장점들과 단점들이 있다.
* 원문에는 "linear data of similar type"이라 쓰여져 있던 부분이다.
Linear data는 Linear(선형) 구조의 data라 이해했다.
Linear(선형) 구조는 데이터가 순차적으로 나열된 구조로, 전후 관계가 1:1로 연결되어 있다.
Stack, Queue, Array, Linked List 모두 Linear 구조이다.
Tree, Graph는 1:n, n:m으로 연결된 비선형 구조이다
Key Differences Between Array and Linked List
-
Data type
- Array는 비슷한 유형의 데이터 집합을 저장하는 자료 구조이다.
- Linked List는 순서가 없이 연결된 데이터 집합(Node)을 저장하는
참조형(non-primitive) 자료구조이다.
-
Seach
- Array는 index로 데이터의 위치를 나타낸다. 만약 4번째 데이터를 알고 싶다면,
Array 변수를 index를 넣은 대괄호([])와 함께 입력하면 된다.
- Linked List는 head부터 시작해서 4번째 데이터를 얻을 때까지 찾아야 한다.
- 즉, 데이터를 찾는 것은 Array가 빠르고,
Linked List는 선형 시간(linear time)이 걸리기 때문에 조금 느리다.
-
Insertion, Deletion
- Array에서 추가(Insertion)와 삭제(Deletion)는 많은 시간이 소요된다.
(ex, index 0번째 데이터가 삭제되면 그 뒤의 모든 데이터가 앞으로 이동해야된다.)
- 반면, Linked List의 추가(Insertion)와 삭제(Deletion)는 빠르다.
(ex, Node를 삭제 할 때, 삭제 Node의 '다음' 정보를 이전 Node의 '다음' 정보로 연결한다.
-
Size
- Array의 Size는 고정되어 있다.
- Linked List는 유동적이고 유연하며, 그들의 Size를 확장하고 축소할 수 있다.
(Array도 Size는 바꿀 수 있지만, 처음에 만들어질 때 Size가 고정되는 반면,
Linked List는 Size가 고정 되지 않고, 바로 추가/삭제된다.)
-
Memory
- Array는 Compile time(컴파일 타임) 동안 할당된다.
- Linked List는 실행 or Runtime(런타임) 동안 할당된다.
(Compile time: 개발자가 작성한 소스 코드가 기계어 코드로 변환되어 실행 가능한 프로그램이 되는 과정)
(런타임: 컴파일 과정을 마친 응용프로그램이 사용자에 의해 실행되어 지는 '때(Time)')
-
Store
- Arrary에서는 연속적으로(consecutively) 저장된다.
- Linked List에서는 랜덤하게(randomly) 저장된다.
-
Requirement of memory
- Array는 Actual Data가 Index로 저장되어 메모리 요구사항이 적다.
- Linked List는 이전과 다음 데이터의 참조를 위해 더 많은 메모리가 필요하다.
-
Memory utilization
- Array는 Memory utilization(메모리 활용도)이 비효율적이다.
(ex, 빈 배열의 4번째 index에 데이터를 바로 저장하면, 0 ~ 3번째는 undefined가 저장된다.
즉 0~3번째는 빈 상태로 저장되므로 메모리 활동도가 좋지 않다.)
- Linked Lists는 Memory utilization(메모리 활용도)이 효율적이다.
Following are the points in favor of Linked Lists.
-
Array의 사이즈는 고정된다.
- 그래서 사전에 저장할 수 있는 데이터의 상한선(upper limit)을 알아야한다.
- 또 사용여부와 상관없이 할당된 메모리의 상한선은 같다.
- 실제로 상한선에 도달하는 건 드물다.
-
새로운 데이터를 Array에 넣는 것은 비용이 많이 든다.
(원문에 expensive로 표현 되어있는데,, '비싸다' 라는 표현이 맞나?)
왜냐하면 새로운 데이터를 위해 room을 만들고,
기존 요소를 이동하기 위해서 room을 만들어야 하기 때문이다.
- 예를 들어, 정렬된 id 리스트가 담긴 "Array id"를 가정하자.
id[] = [1000, 1010, 1050, 2000, 2040, …..]. 만약 우리가 새로운 ID 1005를 넣고 싶고, 순서를 유지하고 싶다면,
"id 1000"을 포함하여 "id 1000" 뒤의 모든 아이디를 이동시켜야 한다.
- 특별한 기술이 사용되지 않는다면 삭제 역시 비싸다.
예를 들어, "id 1010"를 삭제하고 싶다면, "id 1010" 뒤의 아이디를 이동해야한다.
그래서 Linked List는 Array와 다른 2가지 이점이 있다.
- 유동적인 size (Dynamic size)
- 추가/삭제의 용이성 (Ease of insertion/deletion)
Linked list는 다음과 같은 단점이 있다.
- Random access는 허용되지 않는다. 첫번째 node 부터 순차적으로 찾아야한다.
그래서 binary Search는 Linked List와 함께 사용하지 않는다.
- pointer를 위한 여분의 memory 공간이 list의 각 데이터와 함께 필요하다.
(이전/뒤의 Node 정보를 알려주는 pointer를 저장하기 위한 별도 공간이 필요하다.)
- Array는 cache locality가 뛰어나서 성능적인 측면에서 큰 차이점이 발생할 수 있다*.
* 이 부분에 대한 추가 설명은 stackoverflow에 설명되어있다.
내가 이해한 바로는 데이터가 저장될 때 Array는 Memory 블록이 연속적인데,
Linked Lists은 연속적인 Memory일 필요가 없어서 Memory 블록이 띄엄띄엄(?) 있다.
즉, 데이터를 찾아갈 때 시간이 더 걸린다는 얘기 아닐까?
(위에서 'key difference'로 정리한 'store' 부분 이라고 생각한다.)
stackoverflow 글을 꼭 확인하세요!
*출처: Why does cache locality matter for array performance?
Linked List vs Array ??
Insertion/Deletion이 자주 발생한다면 Linekd List,
Search를 하는 경우가 많다면 Array가 더 유리해보인다.
참고