26. List와 Linked List

자료구조를 배우면서, 그리고 다루면서, 지금 시점에서 가장 자주 사용하는 자료구조를 고르라고 하면 나는 List를 고를 것 같다.

 

c#의 List는 배열 기반의 자료구조로써, 자료구조 이전에 사용하던 배열들을 다룰 때와 유사하게 관리할 수 있기 때문에 그런 것 같다.

 

오늘은 이 List에 대해 알아보고, Linked List와 비교하면서 Linked List는 무엇인지, List와 다른 점은 어떤 것인지 알아보도록 하겠다.

 

 

 

 

먼저, c#의 List에 대해 알아보자.

 

List는 앞서 말했듯 배열 기반의 자료구조이다. 따라서 각 항목별로 index가 부여되어있으며, 그 index를 통해 자료에 접근할 수 있다.

 

또한, 배열과 마찬가지로 index에 접근하여 해당 데이터를 초기화하여 수정하는 것도 가능하다.

 

List의 큰 특징 중 하나는 자료의 중간 삽입 및 삭제가 가능하다는 것이다.

 

우리가 이전에 배웠던 Stack과 Queue는 마찬가지로 배열기반이긴 하나 중간삽입이 불가능하였다.

 

하지만 List는 중간 삽입이 가능하며, 중간 데이터를 삭제하는 것도 가능하다.

 

 

 

 

 

이 때, List가 배열기반의 자료구조라면, 중간에 자료가 삽입되거나 삭제됐을 때 빈 공간이 생기게 된다.

 

이러한 경우에, 삽입되었을 때는 삽입하고자 하는 index부터 그 뒤의 자료들을 삽입하려는 만큼 뒤로 밀어버린다.

 

예를들어, 0부터 5번 index에 자료가 들어있는데, 그 중 3번 index에 새로운 자료 하나를 삽입하려고 한다면

3번 index부터 5번 index를 모두 1씩 증가시켜 3번 index의 공간을 확보한 후 그 자리에 자료를 삽입한다.

 

중간삭제의 경우는 3번 index를 삭제하고, 4번 index부터 5번 index를 1씩 감소시켜 그 자리를 메운다.

 

 

 

[0]	[1]	[2]	[3]	[4]	[5]	[6]
0	1	2	4	5	6		[3]에 3을추가
0	1	2		4 ->	5 ->	6 ->
0	1	2	3	4	5	6

[0]	[1]	[2]	[3]	[4]	[5]	[6]
0	1	2	3	4	5	6	[3]의 3을삭제
0	1	2		<- 4	<- 5	<- 6
0	1	2	4	5	6

위의 표 처럼 데이터의 이동이 일어난다.

 

 

 

 

 

List는 동적배열이라고 하는 또다른 특징을 갖고있다.

 

List에 더 이상 새로운 데이터를 추가할 공간이 없는데 새로운 데이터를 추가하려고 하면, 추가하기 전에 배열의 크기를 늘려 메모리 공간을 동적으로 확보한다는 뜻이다. 

 

 

static void Main(string[] args)
{
   List<int> list = new List<int>();
   
   list.Add(1);	//Add()로 값을 추가
   list.Add(2);
   list.Add(3);
   list.Add(4);
   
   Console.WriteLine(list.Capacity);	// 현재 배열크기 4
   
   list.Add(5);	//Add()로 값을 추가
   
   Console.WriteLine(list.Capacity);	// 현재 배열크기 8로 삽입시 크기 증가
   
}

 

위처럼 크기가 4인 배열에 4개의 값이 다 저장되어 더이상 저장할 공간이 없을 때, 새로운 값을 추가하면 동적으로 배열의 크기가 늘어나게된다.

 

 

 

 

위에서 익숙한 <>를 만났다.

 

그렇다. List는 일반화 자료구조로, 다양한 값을 배열처럼 관리할 수 있게 해주는 자료구조이다.

 

이는 비단 기본자료형 뿐만 아니라, 사용자 정의 자료형인 class에도 해당한다.

 

 

 

 

 

 

다음으로는 Linked List에 대해 알아보자.

 

Linked List는 방금 전에 다룬 List와는 다르게, 배열기반의 자료구조가 아니다.

 

Linked List는 Node기반의 자료구조로, 배열과는 다르게 접근하고 관리하여야 한다.

 

 

 

 

Node란, 다른 데이터를 가리키는 참조변수(포인터로 이해하면 쉽다)를 가진 개체를 말한다.

 

이 Node끼리 서로 다음 차례의 데이터를 가리키며 연결되어있는 자료구조가 바로 Linked List이다.

 

node0

(node1을 가리키는 참조변수) ------------>

node1

(node2를 가리키는 참조변수) ------------>

node2

(node3을 가리키는 참조변수) ------------>

node3

(node4을 가리키는 참조변수) ------------>

node4

....

 

위와같이, node들이 각각 다음 node를 가리키며 서로 이어져있다.

 

하지만, 각 node들을 연결짓는 것은 참조변수이지, 실제로 이 node들이 연속된 공간에 할당되어있는 것은 아니다.

 

List는 배열 기반이므로, 서로가 연결된 메모리 공간에 할당되어있지만, Linked List는 연속되지 않은 각각의 메모리 공간에 저장되어있지만, node들이 그들을 연결해주었을 뿐이다.

 

이와같이, 실제로 나란히 줄서있는 List와는 다르게, 각 참조변수를 통해 서로 연결되어 있기 때문에 Linked List라고 이름이 붙여진 것 같다.

 

 

 

 

 

Linked List 역시 List이기 때문에 중간 삽입 및 삭제가 가능하다. 

 

그러나 이 경우에는 Linked List가 List보다 훨씬 효율적인 작업을 수행한다.

 

List의 중간 삽입 및 삭제가 일어났을 때에는, 중간 지점 이후의 모든 데이터들이 움직여야 했다.

 

위의 예에선 크기가 크지 않은 List였지만, List의 크기가 커지면 연산상의 부담도 기하급수적으로 커지게 된다.

 

그러나, Linked List는 그렇지 않다.

 

List는 배열 기반이고, 서로 연속된 메모리 공간에 할당되어있기 때문에 데이터의 이동이 필수적이었지만, Linked List는 Node 기반이다.

 

따라서, 새로운 데이터를 중간에 삽입하거나 삭제할 때, 양 옆의 Node가 가리키는 방향만 바꿔주면 해결된다.

 

말로는 머리에 잘 그려지지 않으니, 표를 통해 이해해보자

 

 

 

	Node1
	│            ▼
Node0	─ ─ ─ ─ ─ ─ ──▶	Node2	─ ─ ─ ─ ─ ─ ──▶	Node3	─ ─ ─ ─ ─ ─ ──▶

 

위의 표 처럼, Node1을Node0과 Node2 사이에 삽입하고자 할 때,

 

┌─ ─ ─ ─ ─ ─ ▶	Node1	┐
│		▼
Node0		Node2	─ ─ ─ ─ ─ ─ ──▶	Node3	─ ─ ─ ─ ─ ─ ──▶

이렇게, Node2를 가리키던 Node0의 참조변수를, Node1을 참조하게끔 수정하고, Node1이 Node2를 가리키게만 수장하면 끝이다.

 

이렇듯, Linked List는 List보다 중간 삽입 및 삭제에 필요한 연산이 굉장히 적다.

 

따라서, 중간 삽입 및 삭제가 잦은 자료를 관리할 때에는 List보다는 Linked List를 사용하여 관리하는 것이 더 유리하다고 할 수 있다.

 

 

 

 

 

이러한 장점만 있는 것이 아니라, Linked List는 List와 비교했을 때의 단점도 존재한다.

 

먼저, 배열기반 자료구조가 아니기 때문에, Index를 통한 자료의 접근이 불가능하다.

 

즉, 배열처럼 관리하기 힘들다는 것이다.

 

For문을 통한 반복문 속에서 index를 활용해 간편하게 데이터에 접근할 수 있었던 List와는 달리, Linked List는 각각 Node에 일일히 접근해, 원하는값을 찾아야 한다.

 

물론, 이것을 전부 사용자가 네이티브로 구현하지 않아도, Linked List의 빌트인 메서드로 찾을 수 있지만, List보다 쉽다고 말할 수는 없다.

 

따라서, 각 요소를 참조할 일이 잦은 자료를 관리함에 있어서는, Linked List보단 List를 사용하는 것이 적합하다고 할 수 있다.