연결 리스트

연결 리스트?

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.

• k번째 원소를 찾기 위해 O(k)의 시간이 필요하다.
• 임의의 위치에 원소를 추가/제거는 O(1)이다.
• 메모리 상에 원소들이 연속해 있지 않으므로 Cache hit rate가 낮지만 할당이 쉬운 편이다.

 

종류

1. 단일 연결 리스트 Singly linked list : 한방향 연결
2. 이중 연결 리스트 Doubly linked list : 양방향 연결
3. 원형 연결 리스트 Circular linked list : 처음과 끝 연결 (양방향, 한방향 둘 다 가능)

 

대표적 선형자료구조인 배열과 연결 리스트의 차이점

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간 (Overhead)	-	O(N)

연결 리스트에서는 추가적으로 다음 원소의 주소값을 가져야 하므로 O(N) 만큼의 메모리를 쓰게 된다.

 

 

연습 문제

 

1. 백준 1406 : https://www.acmicpc.net/problem/1406

var word = Console.ReadLine();
var count = int.Parse(Console.ReadLine());
List<char> list = new List<char>();
int cursor = 0;

if (word != null)
    foreach (char c in word) list.Add(c);
cursor = list.Count;

for(int i = 0; i < count; i++)
{
    var input = Console.ReadLine();
    if(input != null)
    {
        if (input == "L" && cursor > 0) cursor--;
        else if (input == "D" && cursor < list.Count) cursor++;
        else if (input == "B" && cursor > 0)
            list.RemoveAt(--cursor);
        else if (input.Contains("P"))
            list.Insert(cursor++, input[2]);
    }
}
Console.WriteLine(string.Join("", list));

 

 

2. 손코딩 문제 : 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법은?

이때 '효율'은 공간과 시간복잡도를 고려함을 의미한다.

 

A : 동일한 노드가 나올 때 까지 계속 다음 노드로 간다. 공간복잡도 O(1), 시간복잡도O(N).

 

 

3. 손코딩 문제 : 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법은?

 

A : 두 시작점부터 끝까지 진행시켜 두 리스트 각각의 길이를 구한다. 그 후 다시 두 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 이동시키고, 동시에 한 칸씩 전진시켜 만날 때를 구하면 된다. 공간복잡도 O(1), 시간복잡도 O(A+B).

 

 

4. 손코딩 문제 : 주어진 연결 리스트 안에 사이클이 있는지 판단하라.

 

A : Floyd's cycle-finding algorithm 으로 해결이 가능하다. 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있는 경우에 반드시 만나게 되고, 그렇지 않은 경우에 두 커서가 만나지 않고 리스트의 끝에 도달하게 된다. 공간복잡도 O(1), 시간복잡도 O(N).