Array vs LinkedList

📚 Array

Array는 가장 기본적인 자료구조이다. 정적 메모리 할당 방식이기 때문에 stack 영역에 저장된다.

Array는 논리적 저장 순서와 물리적 저장 순서가 일치하는데, 이 말은 배열의 원소가 메모리에 중구난방으로 저장되는 게 아니라 연속적으로 저장된다는 뜻이다. 따라서 처음 저장된 위치만 알면 인덱스를 통해 O(1)의 시간으로 나머지 원소에 접근하는 것이 가능해진다.

인덱스를 통한 접근이 가능하다는 것은 random access가 가능하다는 말과 동일하다.

 

 

 

👍 Array Pros.

1. 논리적 저장 순서 = 물리적 저장 순서(접시가 쌓이듯...)

따라서 찾고자 하는 원소의 인덱스 값만 알고 있으면 O(1)에 해당 원소에 접근하는 것이 가능하다. 

 

2. 자료를 하나의 연속적인 묶음으로 저장하기 때문에 접근이 빠르다.

 

3. 단일한 이름을 사용하여 동일한 유형의 여러 데이터 항목을 표현할 수 있다.

 

 

 

👎 Array Cons.

1. 배열의 크기를 컴파일 이전에 할당해야 헌다.(정적 메모리 할당)

배열은 그 크기를 중간에 수정할 수 없다. 왜나하면 배열을 확장하기 위해서는 다음 메모리 위치를 내가 사용해야 되는데, 이게 이미 사용되고 있는 주소인지 비어있는 주소인지 확신할 수 없고 실수로 다른 데이터를 덮어쓸 위험이 있기 때문에 런타임에 크기를 수정할 수 없는 것이다.

따라서 배열의 크기를 잘못 예측할 경우 저장 공간이 부족하거나 메모리가 낭비되는 일이 발생한다.

 

2. 원소 삽입시 최악의 경우 O(n)

만약 첫번째 자리에 새로운 원소를 추가하려면 모든 원소들의 인덱스를 1씩 shift 해줘야 한다. 이 과정에서 O(n)만큼의 시간 복잡도가 발생한다.

 

3. 원소 삭제시 최악의 경우 O(n)

원소를 삭제할때도 마찬가지로 최악의 경우 O(n)의 시간 복잡도가 발생한다.

배열의 특정 원소를 삭제하려는 경우 배열의 연속적인 특성이 깨지면서 빈 공간이 발생한다.

이때 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용이 발생하고, 만약 첫 번째 원소를 삭제하고자 하는 경우였다면 뒤의 원소를 전부 앞으로 한 칸씩 옮겨줘야 하기 때문에 O(n)만큼의 시간 복잡도가 발생한다.

 

 

 

⛓ Linked List

Array의 단점을 보완하기 위해 등장한 자료구조이다.

Tree 구조의 기반이 되는 자료구조로, 동적 메모리 할당 방식이기 때문에 Heap 영역에 메모리거 할당된다.

"linked"라는 단어 뜻 그대로, 자료들이 포인터라는 개념으로 서로 연결되어있는 자료구조이다.

내가 추가할 자료가 생기면 마지막 자료에 링크로 나를 연결시키기만 하면 된다.

 

 

 

👍 Linked List Pros.

1. 원소를 프로그램 실행 중에 동적으로 생성하거나 삭제할 수 있다.

따라서 배열처럼 리스트의 크기를 미리 예측할 필요가 없어진다.

 

2. 삽입과 삭제가 쉽다.

 

 

 

👎 Linked List Cons.

1. 검색, 삽입, 삭제 모두 최악의 경우 O(n)

배열에서는 삽입과 삭제 과정에서만 최악의 경우 O(n)의 시간 복잡도가 발생했지만 LinkedList는 검색에도 최악의 경우 O(n)이 발생할 수 있다.

삽입과 삭제 자체는 O(1)의 시간복잡도만 발생하지만, linked list에는 인덱스라는 개념이 없기 때문에 내가 삽입할 위치를 찾을 떄까지, 삭제할 원소를 찾을 때까지 리스트의 처음부터 탐색해봐야 되기 떄문이다. 

 

2. 논리적 저장 순서 != 물리적 저장 순서

Linked List가 원소 검색에 있어서 최악의 경우 O(n)의 시간 복잡도가 발생하는 이유이다.

배열에서는 다음 원소가 메모리 상에서 무조건 내 옆에 있다는 것이 자명하지만, linked list의 경우 분산되어있는 자료들을 끈으로 연결만 시켜놓은 것이기 때문에 메모리 주소가 규칙적이지 않다. 일단 아무 데나 자료를 생성해놓고 포인터로 연결하는 식이다.

 

3. 포인터를 위한 추가 공간이 필요하다.

배열은 해당 칸에 원소만 저장하면 되지만, linked list의 경우 다음 원소의 위치를 저장하고 있어야 하기 때문에 이를 위한 추가 공간이 필요하다.

 

4. 종속적인 관계

Linked List는 한 노드가 다음 노드를 가리키고 있기 때문에 노드 간의 종속적인 관계가 형성된다.

따라서 특정 노드가 손실될 경우 이 노드가 가리키고 있던 다음 노드는 접근이 불가능해진다는 문제가 발생한다.

 

 

 

⚡️ 한눈에 비교하는 Array vs Linked List

Array	Linked List
자료가 연속적으로 저장됨	자료가 연속적으로 저장되지 않음
고정된 크기	동적인 크기
메모리가 컴파일 타임에 할당됨	메모리가 런타임에 할당됨
적은 메모리 사용(Data만 저장)	많은 메모리 사용(Data, 다음 노드 주소)
원소 접근 쉬움(인덱스)	원소를 처음부터 다 탐색해봐야 함
삽입, 삭제 O(n)	삽입, 삭제 O(1)

 

 

 

💡 Array를 기반으로 Linked List 구현하기

메모리를 동적으로 할당받을 수 없는 경우 Array을 기반으로 Linked List를 구현해야되는데 어떻게 하면 될까?

생각보다 간단하다.

Linke List의 구조가 Array와 다른 점은 다음 노드를 가리키고 있는 포인터가 있다는 것이다.

그래서 값만 저장하고 있던 배열에 다음 노드의 위치 정보만 추가로 저장해주면 된다.

즉, 2차원 배열을 만들어서 [i][0] = 원소, [i][1] = 포인터 이런 식으로 저장하면 된다. 

 

[0] -> {"a",1}
[1] -> {"b",2}
[2] -> {"c",4}
[3] -> {"1",5}
[4] -> {"d",7}
[5] -> {"2",6}
[6] -> {"3",8}
[7] -> {"e",-1}
[8] -> {"4",-1}

위와 같이 2차원 배열을 만들었다면

"a" -> "b" -> "c" -> "d" -> "e"

"1" -> "2" -> "3" -> "4"

이렇게 2개의 Linked List가 구현된다.

 

 

 

🔗 References

geeksforgeeks.org/introduction-to-arrays

geeksforgeeks.org/data-structures/linked-list

geeksforgeeks.org/linked-list-vs-array

stackoverflow.com/questions/7665607/how-do-you-implement-a-linked-list-within-an-array