리스트

리스트

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

추상 자료형

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

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

선형 리스트

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

List<int> list = new List<int>();

// # 삽입
// Add()는 리스트의 끝에 데이터를 추가한다.
list.Add(5); // [5]
list.Add(4); // [5][4]
list.Add(3); // [5][4][3]
list.Add(2); // [5][4][3][2]
list.Add(1); // [5][4][3][2][1]

// Insert()는 특정 위치에 데이터를 추가한다.
list.Insert(2, 6); // [5][4][6][3][2][1]

// # 읽기
// 인덱서를 통해 특정 위치의 데이터에 접근할 수 있다.
Console.WriteLine(list[3]); // 3

// # 검색
// Contains()를 통해 데이터의 존재 유무를 확인할 수 있다.
Console.WriteLine(list.Contains(6)); // True
Console.WriteLine(list.Contains(7)); // False

// IndexOf()를 사용하면 데이터가 몇 번째 인덱스에 있는지도 확인할 수 있다.
Console.WriteLine(list.IndexOf(6)); // 2
Console.WriteLine(list.IndexOf(7)); // -1

// # 삭제
// Remove()를 이용하면 특정 데이터를 삭제할 수 있다.
// 중복된 데이터가 있는 경우 첫 번째로 발견된 데이터를 삭제한다.
list.Remove(6); // [5][4][3][2][1]

2

// RemoveAt()은 특정 위치에 존재하는 데이터를 삭제한다.
list.RemoveAt(3); // [5][4][3][1]

성능

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

연결 리스트

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

종류

연결 리스트의 종류는 크게 세가지로 나눌 수 있다.

• 단일 연결 리스트(Singly Linked List)
  다음 원소로만 이동이 가능하다.
  
• 이중 연결 리스트(Doubly Linked List)
  이전 원소, 다음 원소 모두 이동할 수 있다.
  
• 원형 연결 리스트(Circular Linked List)
  첫 원소와 마지막 원소가 연결되어 있다.
  

사용법

연결 리스트는 이전, 혹은 이후 데이터를 찾기 위한 참조 타입의 변수가 필요하다.

// 연결 리스트를 구성하는 단위를 노드(Node)라고 한다.
class Node<T>
{
public T Data { get; set; }

// 실제 데이터 말고도 리스트를 구성하기 위한 추가 데이터가 필요하다.
public Node Next { get; set; }
public Node Prev { get;

C#은 LinkedListNode로 구현이 되어 있으며, 연결 리스트는 LinkedList다. LinkedList는 이중 연결 리스트로 구현이 되어 있다.

// 리스트를 생성한다.
LinkedList<int> list = new LinkedList<int>();

// # 삽입
// AddLast()는 리스트의 끝에 데이터를 추가한다.
list.AddLast(5); // [5]
list.AddLast(4); // [5][4]

// AddFirst()는 리스트의 처음에 데이터를 추가한다.
list.AddFirst(1); // [1][5][4]
list.AddFirst(2); // [2][1][5][4]

// # 읽기
// First는 연결 리스트의 첫 번째 노드를 가져온다.
LinkedListNode<int> first = list.First; // [2][1][5][4]
// ↑

// Last는 연결 리스트의 마지막 노드를 가져온다.
LinkedListNode<int> last = list.Last; // [2][1][5][4]
// ↑

// Next 혹은 Previous로 포인터를 이동할 수 있다.
LinkedListNode<int> node = first.Next; // [2][1][5][4]
// ↑

// # 삽입
// AddAfter()를 이용하면 노드 다음에 데이터를 추가할 수 있다.
list.AddAfter(first, 10); // [2][10][1][5][4]

// AddBefore()을 이용하면 노드 이전에 데이터를 추가할 수 있다.
list.AddBefore(node, 8); // [2][10][8][1][5][4]

// # 검색
// Contains()를 통해 데이터의 존재 유무를 확인할 수 있다.
Console.WriteLine(list.Contains(10)); // True
Console.WriteLine(list.Contains(13)); // False

// Find()를 통해 데이터를 저장하고 있는 노드를 가져올 수 있다.
// Null일 수 있다.
Console.WriteLine(list.Find(8)?.Value); // 8

// # 삭제
// Remove()를 이용하면 특정 데이터를 삭제할 수 있다.
list.Remove(10); // [2][8][1][5][4]
list.Remove(6); // [2][8][1][5][4]

// 삭제할 노드를 넣어도 된다.
list.Remove(list.Last.Previous); // [2][8][1][4]

성능

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

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

요약

• 리스트
  데이터간 순서가 있는 자료구조
• 리스트 종류
  • 선형 리스트
    • 성능
      읽기 : O(1)
      검색 : 선형 검색시 O(n), 이진 검색시 O(logN)
      삽입, 삭제 : 처음과 끝일 경우 O(1), 그 외는 O(n)
  • 연결 리스트
    • 성능
      읽기 : O(n)
      검색 : O(n)
      삽입, 삭제 : 노드의 위치를 안다면 O(1), 모르면 O(n)