[C#] 연결 리스트

[연결 리스트(LinkedList)]

 

연결 리스트는 데이터를 포함하는 노드들을 양방향 혹은 한방향으로 연결하여 만든 자료구조이다. 노드는 데이터와 이전,다음 노드 객체를 참조하는 형식으로 구성되어 있는데 노드는 메모리에 연속적으로 배치되지 않는다.

 

 

 

배열은 인덱스를 통해 요소들에 접근할 수 있지만 메모리상 독립적으로 위치해 있는 노드들에 접근하려면 노드들은 각자가 데이터를 가지고 다음 노드나 이전 노드에 대한 위치 정보에 대해 가지고 있어야 한다. 따라서 C#에서는 LinkedList<T> 클래스와 별개로 LinkedList<T> 클래스로부터 생성된 객체를 이루는 것은 단일 정보들의 나열이 아닌 각 노드들이다.

 

인덱스가 존재하지 않기 때문에 노드를 기준으로 연결 리스트에 요소를 추가하고 삭제할 수 있다.

 

 

 

마찬가지로 링크드 리스트는 인덱스를 사용할 수 없기 때문에 0부터 시작해서 길이보다 작은 수가 될 때까지 순회하는 for문으로 요소들에 접근할 수 없다. 다만 노드를 기준으로 전과 후에 있는 요소들은 비교가 가능하기 때문에 연결 리스트의 첫번째 노드를 기준으로 시작해서 다음 노드가 null이 아닐 때까지 요소들에 접근 시킬 수 있다.

 

 

 

 

 

이러한 연결 리스트는 접근과 탐색에 있어서 시간 복잡도는 0(N) 이고 삽입과 삭제에 있어서 시간 복잡도는 0(1)이다.

삽입과 삭제가 빠르게 이루어지기 때문에 삽입과 삭제가 빈번하게 이루어지거나 데이터 크기의 동적 변경이 필요할 경우 이 부분만 봤을 때는 유용하다.

 

하지만 단점들이 존재하는데 삽입과 삭제가 빈번하게 이루어진다는 것은 가비지 컬렉터의 잦은 호출을 유발하고 그에 수반하여 많은 오버헤드를 발생시키므로 오히려 성능에서 저하를 일으킬 수 있고 삽입과 삭제가 이루어지기 전에 먼저 접근과 탐색이 선행되어야 하기 때문에 실질적으로 사용할 때의  시간 복잡도가 더 높은 경우를 초래한다.

 

이에 더해 위치를 인덱스를 통해 접근할 수 있는 동적배열과 배열과는 달리 노드마다 추가적으로 링크가 필요하므로 메모리 소비가 높을 수 밖에 없고 원하는 위치의 요소에 직접 접근하는 데에 시간이 더 소요된다.

 

마지막으로 캐시 메모리에서의 비효율적인 사용이다. CPU와 메모리 사이에 위치하여 CPU의 성능 향상을 위해 사용되는 캐시 메모리는 메인 메모리에 비해 빠른 속도로 접근 가능하며 주로 CPU가 빈번하게 참조하는 데이터나 명령을 임시로 저장하는 역할을 갖는데 이 데이터를 가져올 때 1바이트, 4바이트씩 가져오는게 아니라 캐시 라인, 즉 메모리에서 읽거나 쓸 때의 기본 단위만큼 가져오게 된다.

(만약 CPU가 특정 주소의 데이터를 읽을 때, 해당 데이터가 이미 캐시에 있다면 캐시 라인에 있는 주변의 데이터도 함께 가져와 미래의 참조에 대비한다 이를 공간 지역성이라고 한다. )

 

문제는 이 캐시 라인에 해당하는 데이터 안에 연결 리스트의 데이터가 없을 수 있다는 점이다. 

연속적으로 저장되어 있는 배열과 동적 배열은 한 번 불러들여서 읽을 때 해당 배열의 범위를 모두 읽어낼 수 있지만 연결 리스트는 각 노드들이 연속되어 있지 않고 메모리 상 임의의 위치에 읽기 때문에 캐시 라인만큼 불러 들인다 해도 연속적으로 읽을 수 없기 때문에 빠른 캐시 데이터의 이점을 누릴 수 없게 된다.