1️⃣ 리스트란?
보통 리스트는 배열로 구현하는 방법과 노드로 구현하는 방법 두가지가 있는데
노드로 구현하는 방법이 메모리를 효과적으로 사용할 수 있어서 노드로 구현을 많이 합니다.
이러한 리스트를 연결리스트(Linked List)라고 부르며 이 연결리스트는 연결하는 방식에 따라 크게 세가지로 나눌 수 있습니다.
단일 연결 리스트(Singly Linked List)
아래와 같은 그림의 형식을 단일 연결 리스트 라고 하며 한쪽으로만 갈 수 있다는 특징이 있습니다.
이중 연결 리스트(Doubly Linked List)
아래와 같은 그림의 형식을 이중 연결 리스트라고 하며 한 노드가 양쪽의 노드로 이동할 수 있다는 특징이 있습니다.
원형 연결 리스트(Circular Linked List)
아래와 같은 그림의 형식을 원형 연결 리스트라고 하며 맨 앞의노드(Head)와 맨 뒤의노드(Tail)이 연결되어있다는 특징이 있습니다.
2️⃣ 연결리스트의 연산
일단 연산의 종류부터 구분을 해본다면 탐색, 삽입, 삭제가 있을 것입니다.
탐색O(n): 연결리스트에서 탐색은 별도의 인덱스가 없으므로 처음부터 순차적으로 탐색을 진행해야 합니다. 따라서 O(n)의 시간복잡도가 소요됩니다.삽입O(1): 연결리스트에서 삽입은 단순히 링크의 목적지를 새로 삽입할 노드로 놓고 새로 삽입할 노드의 링크를 다음의 노드로 놓으면 되기 때문에 O(1)의 시간복잡도가 소요됩니다.삭제O(1): 연결리스트에서 삭제는 삭제할 노드의 이전노드의 목적지를 삭제할 노드의 이후 노드로 설정해주면 되므로 이또한 O(1)의 시간복잡도가 소요됩니다.
하지만 보통 삽입과 삭제를 하기위해선 탐색이 필요하므로 삽입과 삭제도 총 연산시간은 O(n)의 시간이 걸린다고 할 수 있습니다.
이렇게만 본다면 배열과 삽입 삭제 연산시간은 똑같은데 탐색시간만 느려서 연결리스트는 쓸모없는 자료구조 처럼 보일지 모르나, 메모리상의 이점과 나중에 나올 트리에서 유용하게 쓰이기 때문에 유용한 자료구조라고 할 수 있습니다.
3️⃣ 코드 예제
여기서 위 세개의 연결리스트를 다 설명하기엔 무리가 있는 것 같아 도움이 될만한 코드를 링크걸어 놓도록 하겠습니다.
4️⃣ 연결리스트의 장단점
장점
- 삽입 삭제가 간단하다.
- 필요한 만큼만 메모리를 할당해 주면 되어서 필요한 데이터가 클수록 메모리상의 이점이 있다.
단점
- 탐색하는데 시간이 오래걸린다.
- 배열에는 불필요한 포인터를 위한 메모리가 필요하다.
- 메모리공간상으로 보았을 때 데이터가 순차적으로 저장되지 않는다.
보통 배열과 연결리스트를 구분하여 장단점을 구분하곤 하는데요.
이전에 포스팅했던 배열과 장단점을 비교하며 보는 것이 좋을 것 같습니다.
5️⃣ 마치며
오늘은 연결리스트에 대하여 알아보았습니다.
궁금한 점이 있거나 틀린 점이 있다면 아래 댓글에 남겨주세요!
다음시간에는 스택에 대해서 알아보는 시간을 갖도록 하겠습니다.
읽어주셔서 감사합니다.
