배열 vs 링크드 리스트(Linked List)

 

배열과 링크드 리스트의 비교에서 싱글 링크드 리스트라는 전제 하에 작성하였습니다.

링크드 리스트(Linked List)

메모리는 데이터 조각을 저장하는 셀들의 거대한 집합 같은 형태로 이루어져 있다.

배열 - 연속된 빈 셀 그룹에 데이터를 저장

링크드 리스트 - 인접하지 않은 메모리 셀 묶음

 

 링크드 리스트는 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 링크드 리스트가 배열보다 나은 점 중 하나로 프로그램이 데이터를 저장하기 위해 메모리 내에 나란히 이어진 빈 셀 묶음을 찾을 필요가 없다는 것이다. 프로그램은 서로 인접하지 않은 여러 셀에 걸쳐 데이터를 저장할 수 있다.

 

 링크드 리스트의 서로 인접하지 않은 이러한 셀을 '노드'라고 한다. 각 노드는 노드에 저장된 데이터뿐만 아니라 연결 리스트 내에 다음 노드의 메모리 주소도 저장해야 한다. 즉, 한 노드에 메모리 셀 두 개씩(데이터 하나, 다음 노드 주소 하나) 사용한다. 

 

배열 vs 링크드 리스트

✱읽기

 

배열	O(1)
링크드 리스트	O(N)

 

 프로그램이 링크드 리스트의 인덱스 2 값을 읽으려고 할 때, 컴퓨터는 배열처럼 바로 찾을 수 없다. 컴퓨터가 알고 있는 것은 첫 번째 노드(head node)의 메모리 주소만 알 뿐이다. 따라서 인덱스 2(세 번째 노드)를 찾으려면 링크드 리스트의 인덱스 0부터 시작해서 다음 노드 주소를 따라 건너 건너 인덱스 2에 있는 값을 확인해야 한다.

 

 컴퓨터가 어떤 인덱스에 있는 값을 찾을 때 최악의 시나리오는 리스트의 마지막 인덱스를 찾는 것이다. 이때 컴퓨터는 리스트의 첫 번째 노드부터 시작해서 마지막 노드까지 각 링크를 따라가야 하므로 N단계가 걸린다. 그래서 링크드 리스트의 효율성은 O(N)이다. O(1)인 배열 읽기에 비해 비효율적이다.

 

 

✱검색

 

배열	O(N)
링크드 리스트	O(N)

 

 검색은 어떤 데이터를 찾고 그 인덱스를 얻는 것이다(indexOf). 배열이든 링크드 리스트든 프로그램은 검색하고 있는 값을 찾을 때까지 첫 번째 셀부터 모든 셀을 하나씩 확인해야 한다. 만약 검색하고 있는 값이 마지막 셀이거나 없는 최악의 시나리오 일 때 O(N)단계가 걸린다.

 

 

✱삽입

 

배열	O(N)  /  앞: O(N),  뒤: O(1)
링크드 리스트	O(N)  /  앞: O(1),  뒤: O(N)

 

 배열에서 삽입할 때 최악의 시나리오는 인덱스 0에 데이터를 삽입할 때이다(unshift). 나머지 데이터를 한 셀씩 옮겨야 하므로 효율성이 O(N)이다. 반면 링크드 리스트는 인덱스 0에 삽입하는 데 딱 한 단계 O(1)만 걸린다. 삽입할 새 노드를 생성하고, 새 노드의 다음 노드의 주소(next)를 원래 제일 앞에 있던 노드를 가리키게끔 하면 된다. 따라서 배열과 달리 링크드 리스트는 데이터를 하나도 시프트하지 않고 리스트 앞에 데이터를 삽입할 수 있다.

 

 그러나 맨 앞이 아니라 중간에 삽입할 때는 배열과 같이 O(N)이 걸린다. 중간에 삽입하려면 중간의 인덱스까지 가기 위해 노드를 건너 건너 찾아가야(검색) 하기 때문이다.

 

 정리하면, 앞에 삽입은 링크드 리스트가 좋고, 끝에 삽입은 배열이 좋다. 배열과 링크드 리스트의 최선, 최악의 시나리오가 서로 정반대이다.

 

 

✱삭제

 

배열	O(N)  /  앞: O(N),  뒤: O(1)
링크드 리스트	O(N)  /  앞: O(1),  뒤: O(N)

 

 배열은 마지막 원소를 삭제할 경우(pop)는 O(1)이지만, 첫 번째 원소를 삭제할 경우 나머지 데이터를 모두 한 셀씩 왼쪽으로 시프트해야 하므로 O(N)이다. 

 

 링크드 리스트는 첫 번째 노드를 삭제하려면 한 단계 O(1)이 걸린다. 마지막 노드를 삭제하는 경우 실제 삭제에는 한 단계 O(1)만 걸리지만 마지막 노드까지 찾아가야 하는 과정에서 O(N)이 걸린다. 링크드 리스트의 마지막 노드 삭제 과정을 말하자면, 다음 노드 주소(next)를 null로만 바꿔주면 되기 때문에 삭제하는 과정 자체는 O(1)이다. 마지막 노드까지 찾아가는 과정이 있어 O(N)인 것.

 

정리

 검색, 삽입 삭제는 비슷하고, 읽기에서는 배열이 더 효율적이다. 그렇다면 왜 링크드 리스트를 사용하려고 하는 것일까?

 링크드 리스트가 빛을 발하는 경우는 많은 원소를 삭제할 때이다. 배열에서는 삭제할 때마다 빈 공간을 메꾸기 위해 나머지 데이터를 왼쪽으로 시프트 해야 하는 또 다른 O(N) 단계가 필요하다. 하지만 링크드 리스트에서는 삭제가 필요하면 노드의 링크가 적절한 노드를 가리키도록 바꾸면 되므로 삭제는 딱 한 단계 O(1)이 걸린다. 

 

 

---

참고

책 - 제이 웬그로우〔누구나 자료 구조와 알고리즘〕