개요

• 리스트는 순서를 가지고 있는 자료구조다.
• 순차 자료구조에는 선형 리스트가 있다.
• 연결 자료구조에는 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.
• 리스트는 다른 자료구조의 기본이 된다.

추상 자료형

• 리스트는 연산에 대해 아래와 같이 동작해야 한다.

1. 읽기 : 인덱스 혹은 반복자를 통해 특정 원소에 접근해야 함
2. 검색 : 특정 원소 혹은 특정 범위의 원소들을 검색할 수 있어야 함
3. 삽입 : 리스트에서 아무 위치에나 원소가 삽입되어야 함
4. 삭제 : 리스트에서 특정 원소를 삭제해야 함

선형 리스트

• 선형 리스트는 순서 리스트라고도 한다.
• 순차적으로 구현한 것이기 때문에 임의 접근이 가능하다.

1. 주소 연산이 가능하기 때문

사용법

성능

• 각 연산에 대한 성능이다.

1. 읽기 : 선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸림
2. 검색 : 하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸림. 단, 정렬되어 있다면 이진 검색을 사용할 수 있고 이 경우에는 O(logn)
3. 삽입 : 위치에 따라 시간이 달라짐. 맨 끝의 경우 O(1)이지만, 처음이나 중간지점이라면 모든 데이터를 이동해야 하기에 O(n)
4. 삭제 : 위치에 따라 시간이 달라짐. 맨 끝의 경우 O(1)이지만, 처음이나 중간지점이라면 모든 데이터를 이동해야 하기에 O(n)

연결 리스트

• 연결 리스트는 메모리에 연속적으로 배치되어 있지 않아 임의 접근이 불가능하다.

1. 주소 연산 불가능

종류

• 연결 리스트의 종류는 크게 세 가지다.

1. 단일 연결 리스트 : 다음 원소로만 이동할 수 있음
   

2. 이중 연결 리스트 : 이전 원소, 다음 원소 모두 이동할 수 있음
   

3. 원형 연결 리스트 : 마지막 원소와 첫 번째 원소를 연결한 형태 (꼬리물기)
   

사용법

• 연결 리스트는 이전 혹은 이후 데이터를 가리키기 위한 참조 타입의 변수가 필요하다.
• C#은 LinkedListNode로 구현이 되어 있으며, 연결 리스트는 LinkedList다.

1. LinkedList는 이중 연결 리스트로 구현이 되어 있다.
   
   

성능

• 연결 리스트의 각 연산에 대한 성능은 아래와 같다.

1. 읽기 : 연결 리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 하므로 O(n)의 시간이 걸리지만, 처음과 끝이라면 구현에 따라 O(1)이 될 수 있음
2. 검색 : 하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸리고, 선형 리스트와 다르게 이진 검색을 사용할 수 없음
3. 삽입 : 노드의 위치를 정확히 알고 있다면 O(1)이지만, 노드의 위치를 모른다면 해당 위치까지 검색해야 하기 때문에 O(n)
4. 삭제 : 노드의 위치를 정확히 알고 있다면 O(1)이지만, 노드의 위치를 모른다면 해당 위치까지 검색해야 하기 때문에 O(n)