[자료구조] 연결 리스트(Linked List)는 무엇일까?

오늘은 자료구조 중 하나인 "연결 리스트"에 대해서 정리해보겠습니다!
자료구조, 알고리즘 공부를 꾸준히 해야 하는데 손이 안 가서 큰일이네요.. ㅠㅠ

 

연결 리스트(Linked List)란?

연결 리스트(Linked List)는 각 노드가 '데이터'와 '포인터'를 가지고 한 줄로 연결되어 있는 자료구조이다.

 

위에서 노드에는 '데이터'와 '포인터'를 가지고 있다고 하였는데 포인터는 무엇일까?

 

검색해본 정의로는 "포인터는 프로그래밍 언어에서 다른 변수, 혹은 그 변수의 메모리 공간 주소를 가리키는 변수를 말한다." 라고 쓰여있다.

 

좀 더 이해하기 쉽도록 말하면 "다음 노드의 주소값을 가지며, 그다음 노드와 연결을 담당해주는 역할"이라고 생각하면 될거같다.

 

참고로, 연결 리스트에는 단방향, 양방향 연결 리스트 등이 있는데, 바로 밑에서 설명할 단방향 연결 리스트는 연결 리스트와 같은 의미로 보면 된다.

 

배열과 연결 리스트

연결 리스트와 배열은 서로의 장단점을 보완해주고 있기 때문에, 보통 연결 리스트를 설명할 때 배열과 묶어서 설명한다.

 

 

배열은 위의 이미지와 같이 데이터가 나란히 있기 때문에 값에 대한 접근이 매우 빠르다.

 

하지만, 처음이나 마지막 부분이 아닌 예를 들어서 중간 요소를 삭제하거나 삽입할 경우에는 요소들을 "재배열해주어야 하는 추가적인 작업"이 필요하다는 단점이 있다.

 

연결 리스트는 배열처럼 순차적으로 데이터를 보관하는 것이 아닌, 떨어진 공간에 존재하는 데이터를 연결시켜둔 것이다.

 

따라서, 연결 리스트는 배열과 다르게 필요한 경우 메모리에 공간을 할당해서 사용하고 요소를 중간에 삽입하거나 삭제해도 연결만 바꿔주면 되므로, 값을 전부 재배열하는 등의 추가적인 작업이 필요하지 않다.

 

반면에, 연결 리스트는 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없기 때문에 배열에 비해 탐색 속도가 느리다는 단점이 있다.

 

거기다가 현재 데이터의 다음 데이터에 대한 연결 정보까지 저장해두어야 하기 때문에, 별도의 공간이 필요해서 효율이 좋지 않다.

 

단방향 연결 리스트(Singly Linked List)

단방향 연결 리스트는 가장 단순한 형태의 연결 리스트이다.

 

위에서 설명했듯, 하나의 노드 안에는 위의 사진과 같이 '데이터' 와 '포인터' 로 구성되어있다.

 

이 자료구조는 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우, 체인이 끊어진 것처럼 뒤쪽의 자료들과 연결이 끊기게 된다. 그러므로 안정적인 자료구조라고는 할 수 없을 것이다.

 

이를 보완하는 방법은 바로 다음에 설명할 양방향 연결 리스트이다.

 

양방향 연결 리스트(Doubly Linked List)

양방향 연결 리스트는 순차적으로 자신이 원하는 데이터까지 하나하나 다 훑고 가야 하는 단방향 연결 리스트의 단점을 보완한 연결 리스트이다.

 

양방향 연결 리스트는 '다음 데이터의 주소 값' 그리고 '이전 데이터의 주소 값'을 가지고 있는 연결 리스트이다.

 

즉, 노드 안에 '데이터 값'과 '이전, 이후 데이터의 주소 값'을 가지고 있는 것이다.

 

그러므로 단방향 연결 리스트와 다르게 자신이 원하는 데이터가 앞쪽에 가까우면 'head'부터 찾으면 더욱 빨리 찾을 수 있을 것이며, 뒤쪽에 가까우면 'tail'부터 찾아보면 더욱 빨리 찾을 수 있을 것이다.

 

 

이처럼 양방향 연결 리스트는 뒤로 탐색하는 속도 또한 빠르며, 다음 참조 주소가 끊기게 되어도 이전 노드를 참조하는 주소 또한 있기 때문에, 중간에 노드를 삭제하고 남아있는 노드끼리 연결하거나, 요소를 중간에 추가하기가 쉽다.

 

하지만, 참조가 2개나 있기 때문에 삽입이나 정렬할 경우 해야 할 작업이 더 많으며 자료구조의 크기가 단방향보다 조금 더 커진다는 단점이 있다.

 

원형 연결 리스트(Circular Linked List)

원형 연결 리스트는 단순히 마지막 tail의 원소가 nil대신, head의 처음 원소를 가리키는 연결 리스트이다. 

 

 

위의 사진처럼 모습이 원형처럼 이어져있어서 "원형 연결 리스트"라고 부른다. 

 

 

언제나 틀린 부분이 있거나 오타가 있으면 댓글로 알려주시면 감사하겠습니다!

 

 

Reference

Wikipedia - 연결 리스트

개발자 소들이 님의 단방향 연결 리스트