[c++] LinkedList(링크드리스트) vs Array(배열) 비교

링크드 리스트는 구조체나 배열처럼 C++에서 제공하는 기능이아니다.

 

그렇기 때문에 직접 만들어서 사용해야 하는데, 일반적으로 구조체와 포인터를 사용해서 만들 수 있다.

 

예를들어 우리가 1,2,3,4라는 4개의 데이터를 보관해야 한다고 생각했을때

 

이 4개의 데이터가 배열에 보관된 모습과 링크드 리스트에 보관된 모습을 비교해보자.

 

// 배열

arr : | a | b | c | d |

사용자는 배열의 시작주소(arr = &arr[0])만 보관하고 있으면 된다.

// 링크드 리스트

a -> b -> c -> d

사용자는 첫번째 노드(a)의 위치만 보관하고 있으면 된다. 

 

배열은 차례대로 위치한 공간에 a ,b, c, d를 포함하고 있다.

 

링크드 리스트는 a, b, c, d를 담은 공간이 차례대로 위치하지는 않는다.

그 대신에 a는 b와 연결되고, b는 c와 연결되고, c는 d와 연결되는 방식으로 전체 아이템들을 보관한다.

이름처럼 연결된 리스트이다.

위의 배열과 링크드 리스트를 보면

 

배열의 경우 3에 접근을 하기 위해서는 *(arr+2), arr[2] 등과 같이 한번에 접근이 가능하다.

 

하지만 링크드 리스트는 c가 있는 곳까지 가려면 a,b를 거쳐야 한다.

이렇게 구성된 상태에서 사용자가 배열과 링크드리스트를 사용하는 시나리오를 생각해보자.

 

먼저 배열은 각 원소들이 차례대로 줄지어서 위치하기 때문에 이렇게 단순한 덧셈을 통해 원소에 접근이 가능하다.

 

하지만 링크드리스트는 배열처럼 차례대로 위치한것이 아니기 때문에 첫번째 노드부터 하나씩

거쳐가면서 c을 보관한 곳을 찾아가야 한다. 

 

구체적으로 말하면 일단 첫번째노드(a)에 접근해서 두번째 노드(b)의 위치를 알아내고, 다시 두번째 노드(b)에 접근한뒤

다음엔 세번째 노드(c)의 위치를 알아낼 수 있다. 결국 c를 보관한 노드에 접근할수 있게되는 식이다.

 

여기까지만 보았을때는 배열이 훨신 좋다.

 

어떤 원소에 접근하려고 할때 배열은 덧셈 한번만 하면 끝나지만, 링크드리스트는 첫번째 노드부터 원하는 노드에 이르기까지

모든 노드를 한번씩 거쳐야 하기 때문이다.

하지만 링크드리스트의 진정한 강점은 노드의 삽입과 삭제가 훨씬 간단하다는 점이다.

 

우선 배열과 링크드리스트에 e라는 데이터를 보관할 새로운 공간을 추가하는 시나리오를 생각해보자

이는 두가지로 나누어 볼수 있는데 배열이나 링크드 리스트의 중간에 삽입하는 경우와 끝에 삽입하는 경우가 있다.

 

※원소와 노드

- 배열에서 a,b,c,d를 보관하는 공간을 원소(Elements)라고 부른다.

비슷하게 링크드 리스트에서 a,b,c,d를 보관하는 공간을 노드(Nodes)라고 부른다.

 

// 배열

arr : | a | b | c | d | e

 

배열이 원소 5개를 보관할 수 있을만큼 크게 정의됐다는 가정하에서 끝에 e를 추가할수있다.

 

// 링크드 리스트

a -- b -- c -- d

e를 보관할 노드를 만들어서 d의 노드와 연결시키면 된다.

 

배열의 끝에 e를 포함하는 원소를 추가하려면 처음 배열을 만들 때부터 충분한 크기의 공간을 만들어야 한다.

만약 원소 4개짜리 배열이었다면 실행중에 새로운 원소를 추가하는 것은 불가능하다.

하지만 링크드리스트 경우에는 e를 포함하는 새로운 노드를 만들고, 마지막 노드와 새로운 노드를 연결시켜주면 끝난다.

 

 

이번에는 배열이나 링크드 리스트 중간에 새로운 정보를 삽입하는 시나리오를 보자.

 

우선 배열의 경우 e라는 값을 a와 b사이에 삽입하려면 b~d까지의 원소를 뒤로 한칸씩 밀어내야 한다.

그다음에 기존에 b가 있던 위치를 e에 넣으면 된다. 만약 10000개쯤있는 배열이라면 9999개의 원소를 밀어내야한다.

 

반면 링크드리스트는 a와 b의 연결을 끊은 후에 a와 e, e와 b를 연결시키면 간단하게 끝난다. 

그 뒤에 9999개의 노드가 있더라도 똑같다.

이런식으로 비교를 해봤을때 삽입삭제 면에서는 링크드리스트가 훨씬 압승이라는 점을 느꼈을 것이다.