2. 연결 리스트 (Linked List)

연결 리스트란 ?

 

먼저, List를 생각하면 쭉 ~ 나열되어 있는 것이 떠오르시나요?

연결 리스트는 말 그대로 쭉 ~ 나열되어 있는 것입니다.

하지만 데이터를 서로 연결하고 있는 것이죠.

어? 쭉 ~ 나열되어있고 연결되어있는 것은 '배열' 아닌가요? 

 

맞습니다.

자료구조의 기본이자 데이터가 순차적으로 나열되어 있는 것은 배열입니다.

 

 

그럼 연속된 데이터를 표현하는 방법으로는 배열(Array)가 있는데 왜 Linked List를 사용하나요?

 

 

배열과 Linked List에는 엄연한 차이가 있습니다.

앞선 포스팅에서 각 자료구조는 필요에 따른 사용처가 있고, 사용자가 유동적으로 사용해야 함을 표현했습니다.

그래서 배열이라는 자료구조에 대해 알고 Linked List라는 자료구조와의 차이점을 알아야합니다.

 

차이점을 설명하기 앞서 배열에 대해 따로 작성하지 않고 바로 Linked List 포스트를 작성하는 이유는 프로그래밍 언어를 공부하게되면 배열에 어느 정도 익숙해져 있다고 생각해서 그렇습니다.

제 블로그 JAVA 언어에 대한 포스트( 자바 배열1, 자바 배열2 ) 중 에도 설명이 작성되어 있고요.

 

배열은 서로 순차적으로 연결되어있지만 연결 리스트는 순차적으로 연결되어 있지만 순차적으로 연결되어있지 않습니다.

메모리 상 배열은 데이터들이 하나의 묶음 [.............]으로 묶여있지만 연결 리스트는 데이터가 서로 흩어져 있습니다.

 

일상생활 예시로 들어보겠습니다. 우리는 노래방 -> PC방 -> 영화관을 가기로 했습니다.

어느 한 장소에 {노래방, PC방, 영화관}이 있습니다.

우리는 해당 장소에서 하고 싶은걸 바로 즐길 수 있습니다.

 

그런데 노래방을 갔다가 갑자기 볼링장을 가고 싶은데 해당 장소에는 볼링장이 없습니다.

볼링장을 이용하려면 이 장소에 볼링장을 아예 새로 설치해야하는데 공간이 부족합니다.

전체 건물을 확장하고 볼링장을 추가해야하죠.

 

그런데 한 장소에만 머물러 있지 않고 동선을 미리 짜두었습니다.

A 노래방 -> B PC방 -> C 영화관

우리는 A 노래방을 갔다가 갑자기 D 볼링장을 가고 싶어졌습니다.

그럼 노래방에서 노래를 부르던 중이나 마치고 D 볼링장을 동선에 추가해서 이동할 수 있습니다.

 

위가 배열의 개념이고 아래가 연결 리스트의 개념입니다. 같은 장소에는 없지만 동선에 추가해서 이동할 수 있죠.

연결리스트는 하나의 묶음이 아니라 방향이라서 언제든지 방향을 수정할 수 있습니다.

---

 

{0, 1, 2, 3, 4, 5} 이라는 데이터가 있다고 가정합니다.

탐색 (Search), 5 찾기

 

우리는 배열에서 시작위치(0)부터 마지막 위치(5)까지 알 수 있습니다. (Index)

시작 위치부터 마지막 위치까지 for문을 통해 원하는 값을 찾을 수 있겠죠?

5를 찾는다고 하면 끝까지 탐색해야하므로 이것을 최악의 경우(Big-O), O(N)이라고 하죠.

 

연결 리스트에서는 현재 위치(주소)만 알고 있습니다. (Iterator)

연결 리스트에서 Iterator가 0을 가르키는지, 3을 가르키는지 마지막에 수행했던 연산을 통해 알 수 있습니다.

만약, Iterator가 5의 주소를 가르키고 있다면 Ω (1), 0의 주소를 가르키고 있다면 O(N)

 

즉, 단순한 탐색 면에서는 큰 차이가 없습니다.

 

접근 (Access), 6번 째 데이터 접근 

 

우리는 배열에서 시작위치부터 마지막 위치까지 알 수 있습니다. (Index)

배열에서 5라는 값을 찾을 때 우리는 인덱싱(array[5])을 통해 O(1) 만에 데이터에 접근할 수 있습니다.

 

연결 리스트에서는 Index 개념이 없어서 데이터에 접근을 하고 싶어도.. 바로 할 수는 없습니다.

현재 위치만 가지고 있으니까요.

만약에 현재 위치가 '5'를 가르키고 있고 접근한다면 Ω(1),

현재 위치가 '0'을 가르키고 있다면 5까지 탐색을 진행한 후에 접근할 수 있습니다.

즉, 최악의 경우 탐색 시간이 발생합니다.  O(N)

 

접근은 Array가 더 효율적입니다.

이제부터 Linked List의 장점이 나옵니다.

 

삽입 (Insertion), 6 삽입

 

Array에서 맨 뒤에 값을 삽입한다고 해보죠.

기본적으로는 out of range 오류가 발생할 것 입니다.

우리는 배열을 선언할 때, 크기를 정하고 배열을 할당하죠?

array[6] = {0, 1, 2, 3, 4, 5}와 같이 말이죠.

array의 맥시멈 크기가 6으로 할당되어서 array[6]에 접근 할 수가 없습니다. 

접근을 하더라도 out of range가 발생하는 것이죠.

 

• 해결책

처음부터 array[100]과 같이 선언한다면 공간이 충분하므로 문제는 없습니다.

하지만, 공간을 낭비하게 된다는 단점이 있습니다. 또 모든 데이터의 크기가 100을 초과한다면 ? 

 

배열 크기 재할당

배열의 크기 < 접근하려는 인덱스 라면, 배열의 크기를 재할당하는 방법이 있습니다.

하지만 재할당을 하게 되면 이전의 데이터가 사라지므로 데이터를 복사해두고 다시 전달해야합니다.

시간을 매우 낭비하는 행위죠. O(2N) 정도 되겠네요.

 

처음과 중간에 삽입할 때도 마찬가지입니다.

array[0]에 값을 넣었다면 이후에 있는 값을 다 한칸씩 뒤로 넘겨주어야 합니다.

array[5] -> array[6], array[4] -> array[5] , ... , array[0] -> array[1], array[0] = 0

즉, O(N)이죠.

 

이번엔 Linked List에서 맨 뒤에 값을 삽입한다고 해보겠습니다.

먼저, 현재 위치(Iterator)만 가지고 있으므로 맨 뒤까지 탐색을 해야합니다...

그런 다음 삽입을 해야죠. O(N)입니다.

 

이 때 까지만 보면, 배열보다 좋은게 하나도 없죠..?

하지만 현재 위치 뒤에 값을 삽입한다면 O(1)입니다.

현재 위치의 값은 4이고, 다음 위치의 값은 5입니다.

우리는 6의 다음 위치를 5로 설정하고 4의 다음 위치를 5로 설정할 수 있습니다.

이 때 시간은 O(1)이 되는거죠.

 

위 방식을 채택하면 연결리스트에서는 현재 위치 다음에 값을 삽입한다면 처음, 중간, 마지막 어느 곳에 값을 삽입하든 O(1)이 됩니다.

 

삭제 (Deletion), 5 삭제

 

삽입과 마찬가지입니다.

배열은 하나의 값을 삭제하게 되면 비어있는 곳을 하나씩 앞당겨줘야하므로 O(N)이 됩니다.

 

연결 리스트는 가르키는 방향만 4 -> 5 -> 6 에서 4 -> 6 이 되도록 수정해주면 되죠.

즉 O(1)이 될 수 있습니다.

 

---

사용 용도와 차이점 정리

	배열	연결 리스트
변경	O(1)	Ω (1), O(N)
접근	O(1)	Ω (1), O(N)
탐색	Ω (1), O(N)	Ω (1), O(N)
삽입	O(N)	Ω (1)
삭제	O(N)	Ω (1)

 

배열 : 템플릿 마냥 초기 형태가 갖추어져있고 그 안에 값 변경만 발생하는 경우 ( 성적 )

 

연결 리스트 : 데이터 구조가 빈번하게 변경되는 경우 ( 에디터 )

포스트 및 댓글을 작성할 때, 글자가 작성되고 중간 글자를 지우는 행위