[종만북] 연결 리스트 / 선형 자료 구조

[종만북] 연결 리스트 / 선형 자료 구조

[종만북] 연결 리스트 / 선형 자료 구조

 

연결 리스트

배열의 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는것은 시간이 오래 걸리는 작업이다.
해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문이다.
정확한 수행시간은 삽입이나 삭제 위치에 따라 다르지만, 평균적인 경우 이 작업들에는 원소들의 개수에 선형 비례하는 시간이 소요된다.

• 이와 같은 문제를 해결하기 위해 고안된 자료구조가 연결 리스트(Linked List) 이다.
• 연결 리스트는 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해 준다.
• 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되어 있지만, 연결 리스트는 원소들이 메모리 여기저기 흩어져 있고 각 원소들은 이전과 다음 원소를 가리키는 포인터를 가지고 있는 방식으로 구현된다.

struct ListNode{
    int element;    // 담고있는 원소
    ListNode *prev; // 이전노드 포인터
    ListNode *next; // 다음노드 포인터
};

 

 

연결 리스트 다루기

• 배열과 달리 연결 리스트에서는 메모리 여기저기에 노드들이 흩어져 있기 때문에, 특정 위치의 값을 찾기 쉽지 않다.
  • i 번째 노드를 찾으려면 머리에서부터 시작해 하나씩 따라가며 다음 노드를 찾을 수 밖에 없다.
  • i 번째 노드를 찾는데 드는 시간은 리스트의 길이에 선형 비례하게 된다.
• 다른 노드들의 순서를 유지하면서 새 노드를 삽입하거나 기존 노드를 삭제하는 작업은 간단하다.
  • 노드들의 순서가 포인터에 의해 정의 도기 때문에 포인터만 수정하면 된다.
  • 노드이 삽입과 삭제 시간은 각각 상수 시간에 이루어진다.

 

 

표준 라이브러리의 연결 리스트 구현

• 동적 배열과 같이, 대부분의 프로그래밍 언어에서는 연결 리스트의 구현을 표준 라이브러리에서 제공한다.
  • C++STL 의 list
  • Java 와 C# 의 LinkedList
• 연결 리스트를 직접 구현할 일은 거의 없다.

 

 

연결 리스트 응용 연산들

연결 리스트 응용 연산들 - 잘라 붙이기 연산 (Splicing)

• 연결 리스트에 원소를 삽입/삭제 하는것과 같이, 다른 리스트를 통째료 삽입하는 것 또한 상수시간에 할 수 있다.
• 잘라 붙이기 연산을 사용하면 두 연결 리스트를 상수 시간에 하나로 합칠 수 있지만, 연결 리스트의 크기를 O(1) 에 알기 불가능 해진다.
  • 연결 리스트에서는 크기를 쉽게 알 수 있는 방법이 없어서 원소의 개수를 갱신해 주어야 하는데, 잘라 붙이기 연산을 할 때에는 몇개의 원소가 추가되는지 알 방법이 없기 때문이다.
  • 이와 같은 특성 때문에 잘라 붙이기 연산을 지원하는 연결 리스트 구현은 많지 않다.
  • Java 나 C# 에서는 잘라 붙이기 연산을 포기한 대신, 리스트의 크기를 구하는 연산을 상수 시간에 지원한다.
  • C++STL 의 list 는 splice() 멤버 함수를 통해 잘라 붙이기 연산을 지원하지만, 리스트의 크기를 구하려면 선형시간의 방복문을 수행하여야 한다.

 

 

연결 리스트 응용 연산들 - 삭제했던 원소 돌려놓기

• 양방향 연결 리스트의 잘 알려지지 않은 장점은 한 번 삭제했던 원소를 제자리에 쉽게 돌려 놓을 수 있는 것이다.
• 원소 삭제 시, node 이전/이후 노드의 포인터만 수정되고 삭제된 node 의 정보는 변하지 않기 때문에 자신의 위치를 여전히 알고 있는 상태가 된다.

// 연결 리스트에서 노드를 삭제하고 다시 추가하기

// node 이전/이후 노드의 포인터를 바꿔서 node를 리스트에서 삭제
void deleteNode (ListNode* node){
    // 이전 노드의 next를 node의 뒷 노드로
    node->prev->next = node->next;
    // 이후 노드의 prev를 node의 앞 노드로
    node->next->prev = node->prev;
}

// 노드 이전/이후 노드의 포이터를 바꿔서 자기 자신을 다시 리스트에 삽입
void recoverNode(ListNode* node){
    // 원래 위치 뒷 노드의 next를 node로 설정
    node->prev->next = node;
    // 원래 위치 앞 노드의 prev를 node로 설정
    node->next->prev = node;
}

 

 

동적 배열과 연결 리스트의 비교

• 동적 배열과 연결 리스트의 가장 큰 차이점은 삽입과 삭제 그리고 임의의 원소에 접근하는 시간이다.
• 삽입과 삭제를 할 일이 없거나, 배열의 끝에 서만 하면 될 경우는 동적 배열이 거의 항상 더 좋은 선택이다.
  • 임의의 원소에 빠르게 접근할 수 있을 뿐더러, 원소들이 메모리에 연속해 배치되어 있다는 점이 CPU 캐시의 효율도 더 높여주기 때문이다.
• 임의의 원소를 접근하는 것이 아니라 모든 원소들을 순회하며 삽입/삭제를 한다면 연결 리스트가 좋은 선택이다.

작업	동적 배열	연결 리스트
이전 원소/다음 원소 찾기	O(1)	O(1)
맨 뒤에 원소 추가/삭제 하기	O(1)	O(1)
맨 뒤 이외의 위치에 원소 추가/삭제 하기	O(n)	O(1)
임의의 원소 위치 찾기	O(1)	O(n)
크기 구하기	O(1)	O(n) 혹은 구현에 따라 O(1)