도입

리스트 자료구조는 데이터를 나란히 저장하고, 중복된 데이터의 저장을 막지 않는 자료구조이다.

순서가 있다는 점과 중복을 허용한다는 점에서 집합과 구별되고, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩 있다는 점에서 그래프와도 구별된다.

리스트 자료구조는 구현 방법에 따라서 순차 리스트와 연결 리스트로 나뉜다. 순차 리스트는 배열을 기반으로 구현된 리스트이고, 연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트이다.

배열 기반 리스트 (Array List)

Array List는 추상적 자료형인 리스트를 배열을 사용하여 구현한 자료구조이다.

장점

• 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다. 배열을 선언할 때 정해진 크기만큼 연속된 메모리 주소를 할당 받는다. 이 덕분에 임의의 인덱스로 임의 접근(random access)이 가능하다.

단점

• 연속된 메모리 주소를 할당해야 하기 때문에 배열의 길이가 초기에 결정되어야 한다. 즉 변경이 불가능하다.
• 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

  
  위의 그림처럼 배열에서 특정 값을 삭제하게 된다면 그 값 이후의 값들을 전부 한 칸씩 앞으로 옮겨야 한다. 그렇기 때문에 많은 시간이 소요된다.

연결 리스트 (Linked List)

연결 리스트는 추상적 자료형인 리스트를 구현한 자료구조이다. 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장한다. 각 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.

위의 그림은 4개의 정수를 저장하고 있는 단순 연결 리스트를 나타낸다.

연결 리스트에는 단순(단일) 연결 리스트, 원형 연결 리스트, 양방향(이중) 연결 리스트 등이 있다.

단순 연결 리스트 (Singly Linked List)

단순 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

원형 연결 리스트

원형 연결 리스트는 일반적인 연결 리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

양방향 연결 리스트

양방향 연결 리스트는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

장점

• 데이터의 추가와 삭제가 용이하다.
• 리스트의 크기를 자유롭게 조절할 수 있다. 즉, 크기를 미리 지정할 필요가 없다.

단점

• 배열과 달리 연속적인 메모리 주소를 할당 받지 않기 때문에 임의 접근이 불가능하다. 대신 연결 리스트에서는 탐색을 위해 순차 접근(sequential access) 방식을 사용한다.

시간 복잡도

데이터 탐색

배열 기반 리스트

임의 접근 방식을 사용하기 때문에 인덱스를 이용해 바로 탐색할 수 있다. 따라서 배열 기반 리스트의 탐색 과정의 시간 복잡도는 O(1)이다.

연결 리스트

순차 접근 방식을 사용하기 때문에 어떤 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 한다. 따라서 연결 리스트의 탐색 과정의 시간 복잡도는 O(n)이다.

데이터 추가

배열 기반 리스트

배열 기반 리스트는 데이터들이 순차적으로 저장되어 있다. 따라서 맨 처음이나 그 이후에 데이터를 추가하려면 그 뒤에 있는 데이터들을 전부 한 칸씩 뒤로 옮겨야 한다. 따라서 이때의 시간 복잡도는 O(n)이다. 다만, 맨 뒤에 데이터를 추가할 때는 다른 데이터들의 위치를 옮길 필요가 없으므로 시간 복잡도가 O(1)이다.

연결 리스트

데이터를 추가하는 행위 자체의 시간 복잡도는 O(1)이다. 하지만 데이터를 추가하는 위치가 맨 앞이 아니라면 그 위치까지 순차적으로 탐색하면서 이동해야 한다. 따라서 추가 위치까지 이동할 때의 시간 복잡도는 O(n)이다.
따라서 추가하려는 데이터의 위치가 맨 앞이라면 O(1)의 시간 복잡도를 가지고, 추가하려는 데이터의 위치가 맨 앞이 아니라면 O(n)의 시간 복잡도를 가진다.

데이터 삭제

데이터 삭제의 시간 복잡도가 다음과 같은 이유는 데이터 추가의 경우와 같다.

배열 기반 리스트

삭제하려는 데이터의 위치가 맨 뒤가 아니라면 O(n)의 시간 복잡도를 가지고, 삭제하려는 데이터의 위치가 맨 뒤라면 O(1)의 시간 복잡도를 가진다.

연결 리스트

삭제하려는 데이터의 위치가 맨 앞이라면 O(1)의 시간 복잡도를 가지고, 삭제하려는 데이터의 위치가 맨 앞이 아니라면 O(n)의 시간 복잡도를 가진다.

정리

배열 기반 리스트는 연결 리스트와 비교했을 때 상대적으로 데이터의 접근과 탐색에 우위를 가진다. 연결 리스트는 배열 기반 리스트와 비교했을 때 상대적으로 데이터의 추가와 삭제에 우위를 가진다.
따라서 데이터의 접근과 탐색이 중요한 경우엔 배열 기반 리스트를 사용하고, 데이터의 추가와 삭제가 중요한 경우엔 연결 리스트를 사용하면 된다.