자바에서 ArrayList 클래스에서는 배열을 사용합니다. 하지만 배열은 용량이 정해져 있어 용량을 초과한다면 더 큰 배열을 만들어서 옮기는 과정이 필요합니다. (이러한 과정이 자주 일어난다면 매우 비효율적일 것입니다.)
그리고 배열은 순차적인 삽입/삭제가 아닌 이상 삽입/삭제에서 시간복잡도 O(n)으로 단점을 보이고 있습니다. 그래서 이러한 단점을 보완하기 위해 나온 것이 바로 연결리스트입니다.
연결리스트는 배열과 다르게 데이터들이 메인 메모리상의 흩어져서 존재합니다. 이렇게 물리적으로 흩어져 있는 데이터들을 연결하는 자료구조를 연결리스트라고 합니다.
연결리스트의 종류에는 단일 연결리스트, 이중 연결 리스트, 원형 연결 리스트가 있는데 하나씩 어떤 특징을 가지고 있는지 알아보겠습니다.
단일 연결 리스트는 말 그대로 한 방향(단일)으로만 연결되어 있는 것입니다. 여기서 data-next 네모의 쌍을 노드라고 표현을 합니다. 그리고 data에는 값을 저장하고, next에는 다음 노드의 주소를 저장합니다. (맨 마지막에 더 이상 연결될 노드가 없다면 null을 채웁니다.)
단일 연결 리스트에서는 첫 번째 노드의 주소를 알아야만 전체 연결 리스트에 접근할 수 있습니다. 그래서 첫 번째노드의 주소를 가지고 있는 변수가 필요한데, 그것을 head라고 합니다.
이제 단일 연결 리스트에서 삽입, 삭제, 탐색은 어떻게 이루어지는지 알아보겠습니다.
위와 같은 단일 연결 리스트에서 17의 값을 가진 노드를 탐색 해보겠습니다. 그러면 위에서 말했던 것처럼 head를 통해서 맨 처음 노드에 접근하게 될 것입니다.
위와 같이 맨 처음 노드에 접근하게 됩니다. 그러면 처음 노드에서 두 번째 노드의 주소를 가지고 있기 때문에 찾는 원소가 아니라면 다음 노드로 이동합니다.
그리고 이러한 과정을 계속 반복하게 되면 결국 아래와 같이 원하는 원소를 찾게 됩니다.
단일 연결리스트에서 탐색은 이러한 과정들을 통해서 이루어집니다. 배열은 시간복잡도 O(1)로 원소를 찾을 수 있는 반면에 연결리스트는 O(n)이 걸린다는 단점이 존재합니다.
이번에는 삽입, 삭제에 대해서 좀 더 알아보겠습니다.
단일 연결 리스트에서 노드 21과 노드 17사이에 새로운 노드를 추가하려면 어떻게 해야할까요? 일단 새로운 노드가 추가될 위치 앞에 해당하는 노드까지 탐색해서 가야합니다.
그러면 삽입 할 위치의 앞 노드인 21까지 찾아왔다고 가정하겠습니다. 그 다음에는 어떻게 해야할까요?
노드 21이 가리키는 주소를 84를 가르키게 합니다.노드 84가 가르키는 주소를 17을 가리키게 합니다.(즉, 21이 가리키고 있는 주소를 84가 가르키도록 해야합니다. 주소를 잃어버리지 않도록...)
위와 같이 단일 연결 리스트에서 원소를 삭제할 때는 어떻게 해야할까요? 이것도 삽입과 마찬가지로 삭제를 하기 위한 노드가 가리키는 앞 노드까지 탐색을 통해 이동해야 합니다.
65 노드가 21을 가리키고 있는 주소를 삭제할 노드가 가리키고 있는 주소인 노드 17을 가리키게 하면 됩니다.(주소를 잃어버리지 않도록...)
단일 연결 리스트에서는 마지막 노드는 주소를 저장하는 곳에 null을 저장했습니다. 하지만 원형 연결 리스트에서는 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다.
이렇게 원형 연결 리스트 형태로 저장하면 어떤 장점이 있을까요? 단일 연결리스트는 한방향으로만 되어 있기 때문에 뒤로 돌아갈 수 없고, 맨 처음으로 다시 가기가 힘들다는 단점이 있습니다.
하지만 원형 연결 리스트를 이용하게 되면 하나의 노드를 거쳐서 처음으로 되돌아 올 수 있다는 장점을 가질 수 있습니다. 따라서 원소의 삽입, 삭제가 좀 더 편리해진다는 장점이 생깁니다.
원형 연결 리스트는 첫 노드를 시작해서 다시 처음으로 돌아올 수 있다는 장점이 있다고 하였습니다.
하지만 원형 연결 리스트 형태로 1-2-3-4-5-6-7가 연결된 상태에서 현재 4를 가리키고 있다고 가정하겠습니다. 이 때 3을 찾아야 한다면 어떻게 해야할까요?
맨 뒤인 7까지 간 후에 다시 1로 돌아와서 3을 찾아야 합니다. 그러면 당연히 한칸만 뒤로 가면 되는데 끝까지 가서 다시 처음부터 탐색해야 한다는 단점이 존재하게 됩니다.
또한 단방향 연결리스트에서도 어떤 노드의 후속 노드를 찾는 것은 쉽지만, 선행 노드를 찾으려면 구조상 아주 어렵습니다.
그래서 이러한 단점을 보완하기 위해서 나온 것이 양방향 연결 리스트입니다.
이중 연결 리스트는 앞, 뒤의 주소를 저장하면서 양방향 검색이 가능합니다. 단점으로는 구현이 복잡하고, 메모리 공간을 많이 차지한다는 것이 있습니다.
배열은메모리에 연속적으로 저장한다는 특징을 가지고 있고, 시간복잡도는 위와 같습니다.연결 리스트는메모리에 흩어져서 저장되어 있다는특징을 가지고 있고, 시간복잡도는 위와 같습니다.
그리고 하나 더 보아야 할 점은 연결리스트에는 추가적으로 필요한 공간이 있습니다.
연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야 합니다. 그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하고, 64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요하게 됩니다. 즉, N에 비례하는 만큼의 메모리를 추가로 쓰게 됩니다.