1. Array & Linked List

Array

A ordered sequence of elements of the same type

배열이란 같은 형태의 요소들로 이루어진 자료구조를 말하며 다음과 같은 특징이 있다.

 

- 각각의 element들은 index를 통해 참조한다.

- 특정 순서에 따라 저장하기에 편리하다.

- 미리 크기를 설정해주어야 한다.

 

Search

배열은 i 번째 element를 찾을 때 시작 주소 + ( i × 자료형의 크기 ) 계산만 하면 위치를 찾을 수 있다.

 

따라서 탐색에 걸리는 시간이 상수이므로 시간복잡도는 O(1)이 된다.

 

Insertion

위와 같은 배열에서 2와 6 사이에 4를 넣고 싶다면

 

뒤의 모든 element들을 한칸씩 뒤로 옮겨주어야 한다.

 

따라서 삽입에 element 갯수 n에 비례한 시간이 소모되므로 시간복잡도는 O(n)이다.

 

Deletion

마찬가지로 위의 배열에서 6을 빼고 싶다면

 

6을 빼고 난 후 뒤의 모든 element들을 한 칸씩 앞으로 옮겨주어야 한다.

 

따라서 삭제 또한 시간복잡도 O(n)이다.

 

 

 

Singly Linked List

단일 연결 리스트는 각각의 노드가 데이터와 포인터 정보를 갖고 있는 자료구조이다.

포인터 정보에 다음 노드의 위치가 담겨있어 이전 노드로부터 다음 노드를 찾아갈 수 있다.

 

Search

단일 연결 리스트에서 i 번째 요소를 찾기 위해선 첫 번째 노드 부터 i 개의 요소를 거쳐야 찾을 수 있다.

 

따라서 전체 크기가 n인 단일 연결 리스트에서 탐색에 필요한 최대 시간은 n이므로 시간 복잡도는 O(n)이다.

 

Insertion

위와 같이 구성된 단일 연결 리스트의 1과 5 사이에 3이라는 데이터를 가진 노드를 삽입하고 싶다면

 

 

1. 먼저 데이터를 가진 새 노드를 만들어 준 뒤

 

 

2. 앞의 노드의 포인터를 새 노드로 옮기고

 

 

3. 새 노드의 포인터를 뒤 노드의 위치로 지정해주면 된다.

 

따라서 위치에 상관없이 언제나 3단계만 거치면 되므로 상수, O(1) 시간복잡도를 갖는다.

 

Deletion

삭제는 삽입과 똑같은 과정을 거꾸로 하면 된다.

 

 

1. 삭제할 노드를 없애고

 

 

2. 앞 노드의 포인터를 뒤 노드로 지정해주면 된다.

 

따라서 삽입과 마찬가지로 삭제도 O(1)의 시간복잡도를 갖는다.

 

 

 

Doubly Linked List

이중 연결 리스트는 단일 연결 리스트에 앞 노드의 위치를 저장하는 포인터를 추가한 자료구조이다.

 

Search

탐색은 단일 연결 리스트와 마찬가지로 노드를 하나씩 거치면 된다.

 

이 때, index가 전체 크기의 절반보다 작으면 앞쪽, 크면 뒤쪽부터 찾으면 되므로 worst case는 n/2 cost가 든다.

 

하지만 n/2는 시간복잡도를 표기할 때 n과 동일하므로 단일 연결 리스트와 마찬가지로 시간복잡도는 O(n)이다.

 

Insertion

삽입 과정도 단일 연결 리스트와 비슷하다.

 

위와 같은 연결 리스트에서 1과 3 사이에 2를 추가하려 한다면

 

 

1. 데이터를 담은 새 노드를 만들고

 

 

2. 포인터 연결을 옮겨주면 된다.

 

따라서 삽입의 시간복잡도는 O(1)이다.

 

Deletion

삭제 역시 단일 연결 리스트와 비슷하다.

 

2가 삽입된 연결 리스트에서 2를 다시 삭제하려면

 

 

1. 삭제할 노드를 제거한 뒤

 

 

2. 포인터 연결을 옮겨주면 된다.

 

따라서 삭제의 시간복잡도도 O(1)이다.

 

 

 

Summary

배열 - 탐색 O(1) / 삽입, 삭제 O(n)

연결 리스트 - 탐색 O(n) / 삽입, 삭제 O(1)

 

따라서 탐색이 많이 필요한 작업에는 배열을 사용하고,

삽입, 삭제가 많이 필요한 작업에는 연결 리스트를 사용하는 것이 유리하다.