링크드 리스트(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) 혹은 단일 연결 리스트 이외에도 이중 연결리스트, 원형 연결 리스트, 다중 연결 리스트가 존재한다.
요약
링크드 리스트 자료구조는 배열, 스택, 큐와 다르게 조금 복잡하다. 그러나 유용한 자료구조 이며, 트리(tree) 구조의 근간이 되는 자료구조이며, 트리에서 사용되었을 때 그 유용성이 드러난다.
참고
