🤔 링크드 리스트(Linked List)?
배열(Array)은 순차적으로 연결된 공간에 데이터를 나열하는 자료구조이고, 링크드 리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 자료구조이다. 배열은 미리 특정한 연결된 공간을 확보하고 데이터를 쓰고 있는 자료구조이고, 링크드 리스트는 필요할 때 마다 데이터를 추가할 수 있는 구조이다. 배열의 단점을 극복한 자료구조가 링크드 리스트라고 볼 수 있다.
링크드 리스트(Linked List)의 구조와 용어
링크드 리스트(Linked List)는 연결 리스트(Linked List) 혹은 단일(단방향) 연결 리스트(Singly Linked List)라고도 한다. 배열과 달리 특정한 데이터를 저장할 때 해당 데이터를 저장하는 공간과 함께, 그 다음에 나올 데이터가 저장되어있는 공간을 가리키는 주소값을 동시에 가지고 있다. 링크드 리스트는 이 두 공간을 하나의 데이터로 관리한다.
일반적인 링크드 리스트는 위 그림과 같이 붙어 있는 두 박스 중에 왼쪽에 있는 데이터 값(12, 99, 37)과 오른쪽의 화살표(->)가 하나의 데이터로써 관리 된다. 즉, Node는 데이터 저장 단위(Data + Pointer)로 구성이 되어 있고, Pointer는 각 node 안에서 다음에 연결된 node와의 연결 정보를 가지고 있는 공간이다. 연결 정보는 다음 node의 데이터 주소를 말한다. 첫번째 데이터만 알고 있으면 pointer를 통해 그 다음으로 연결된 모든 데이터를 알 수 있다. 일반적으로 링크드 리스트의 시작이 되는 node는 Head, 마지막 node는 Tail이라고 부른다.
링크드 리스트(Linked List)의 장점과 단점
링크드 리스트의 장점은 배열과 다르게 미리 데이터 공간을 할당하지 않아도 된다. 배열은 미리 데이터 공간을 할당해야 한다. 단점은 첫번째, 연결(pointer)를 위한 별도의 데이터 공간이 필요하므로 저장 공간의 효율이 높지 않다. 현재의 node 안에서 데이터 값만 갖고 있는 것이 아니라 그 다음의 데이터가 올 주소까지 포함해야 하기 때문에 추가적인 데이터 공간이 필요하다. 두번째, 연결 정보를 찾는 시간이 필요하므로 데이터 접근 속도가 느리다. 배열과 같이 특정 index가 존재하는 것이 아니기 때문에 원하는 데이터를 찾기 위해서는 연결된 링크를 따라서 순차적으로 확인하는 시간이 필요하다. 마지막으로 링크드 리스트에 데이터를 삽입 혹은 삭제시 전, 후 데이터의 연결을 재구성해야하는 부가적인 작업이 발생한다.
링크드 리스트(Linked List)의 복잡한 기능
링크드 리스트에서 새로운 node(newNode)를 삽입하려면 부가적인 구현이 필요하다. 위의 그림을 예로 들면 먼저 node를 찾는다. 찾은 node에서 newNode의 주소 값을 node의 pointer로 연결해주고, node.next의 주소 값을 newNode의 pointer로 연결한다.
삭제의 경우 head 삭제, tail 삭제, 중간 node 삭제와 같이 크게 3가지로 나눌 수 있다. 먼저 head 삭제의 경우 head의 다음 node가 head가 되도록 구현한다. tail을 삭제할 경우 tail 앞에 있는 node의 주소값을 null로 변경한다. 마지막으로 중간 node를 삭제하는 경우 먼저 그림과 같이 node를 찾는다. node의 pointer를 node.next에서 node.next.next로 바꾸어 연결해주고 node.next를 삭제하면 된다.
링크드 리스트의 다양한 구조
링크드 리스트는 앞에서 설명한 링크드 리스트(Linked List) 혹은 단일 연결 리스트(Singly Linked List) 이 외에도 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List), 다중 연결 리스트(Multiply Linked List)가 존재한다. 이중에서 이중 연결 리스트에 대해서만 간략하게 알아보려고 한다.
위 그림과 같은 링크드 리스트를 이중(양방향) 연결 리스트 혹은 더블 링크드 리스트(Doubly Linked List)라고 부른다. node의 pointer가 이전 node와 다음 node를 모두 가리키고 있는 것이 특징이다. pointer가 양방향으로 연결되어 있기 때문에 node 탐색이 양쪽으로 모두 가능하다. 예를 들어 찾고자 하는 데이터가 연결 리스트의 뒤 쪽에 존재할 경우 단일 연결 리스트는 처음 node부터 순차적으로 탐색이 필요하다. 그러나 이중 연결 리스트는 마지막 node에서 시작하여 처음 node 방향으로 탐색이 가능하기 때문에 더 빠른 시간 안에 데이터를 찾을 수 있다.
💡 정리
링크드 리스트 자료구조는 배열, 스택, 큐와 다르게 조금 복잡할 순 있다. 그러나 아주 쓸모없는 자료구조는 아니다. 링크드 리스트는 트리(Tree) 구조의 근간이 되는 자료구조이며, 트리에서 사용되었을 때 그 유용성이 드러난다.
📝 참고
ZeroCho Blog - 자료구조(연결 리스트, linked list)
Github - JaeYeopHan/Interview_Question_for_Beginner
[이미지출처] wikipedia - linked list
