java LinkedList 인덱스의 의미

Intro

예전에 공부할 때는 그저 외우는 수준에서 그쳤는데, 오늘은 CS를 준비하면서 그 원리가 궁금해졌다.

그 원리를 파헤쳐 보자우!

 

 

ArrayList vs LinkedList

ArrayList의 경우는 메모리에 저장될 때 연속적으로 저장되고, LinkedList의 경우 메모리에 불연속적으로 저장되나 해당 데이터와 다음 데이터를 가리키는 포인터가 저장되는 노드의 형태로 저장이 된다. 또한 ArrayList는 데이터의 중간 삽입 또는 중간의 데이터를 삭제할 경우 LinkedList에 비해 속도가 느리다. 반면 LinkedList의 경우 해당 노드들이 가리키는 포인터의 값들만 변경하면 되기때문에 ArrayList에 비해 데이터의 중간 삽입 또는 중간 데이터들의 삭제가 더 용이하다고 한다.
 

 

LinkedList는 인덱스가 없는데 왜 get() 메서드가 존재하지?

LinkedList의 경우 특정 값을 탐색할 경우 인덱스가 없으므로 첫 노드부터 순회하며 해당하는 값을 찾아낸다고 알고 있었는데, 코딩테스트에 LinkedList를 사용해 보니 ArrayList처럼 인덱스로 값을 찾아올 수 있는 get() 메서드가 존재했다. LinekdList는 인덱스가 없다면서 왜 인덱스 조회가 가능한 메서드가 존재할까? 이 부분이 예전부터 궁금했는데 오늘은 이 부분을 파헤치기로 했다.
 
LinkedList의 경우 인덱스가 없는것이 맞다고 한다. 정확히 말하자면 값이 저장될 때 해당 데이터와 포인터로만 구성이 되기 때문에 인덱스 번호 또는 해당 노드의 순서가 몇 번째인지에 대한 정보가 따로 저장되지 않는다고 한다.

 

그렇다면 get()메서드를 이용하여 인덱스를 통한 데이터 조회는 어떻게 이루어지는 것일까?

LinedList의 경우는 인덱스번호가 배열에서의 인덱스의 역할을 하는 것이 아닌 'n번째 노드'를 가리킨다.
따라서 인덱스가 없는 LinkedList는 노드를 처음부터 순회하며 현재의 노드가 몇 번째 노드인지 개수를 새어나가며 n번째에 도달하였을 때 그 값을 도출해 낸다. 그렇기 때문에 LinkedList가 ArrayList보다 조회 속도가 느릴 수밖에 없다.
 

그렇다면 LinkedList는 마지막 노드 또한 처음부터 순회하여 찾아낼까?

자바에서의 LinkedList 클래스 안에는 첫 번째 노드와 마지막 노드의 포인터를 저장할 수 있는 멤버 변수가 존재한다. 그 포인터를 이용하여 마지막 노드를 찾아낼 때는 O(n)의 시간복잡도를 갖는 것이 아닌 O(1)의 시간 복잡도를 갖는다.
 

또 궁금했던 점은 그렇다면 n번째 노드까지 도달하기 위해 순회를 한다는 점에서 ArrayList에 비해 시간이 더 오래 걸린다는 것인데, LinkedList는 ArrayList에 비해 데이터 추가, 삭제에 왜 용이할까? 수정, 삭제 시에도 해당 노드까지 도달하려면 ArrayList보다 더 시간이 걸리기때문에 더 오래 걸려야하는것이 아닐까?

그것에 대한 답은 LinkedList의 해당 노드까지의 도달하는 시간보다 ArrayList에서 인덱스 사이에 데이터 추가, 삭제시에 일어나는 연산(데이터 추가, 삭제 인덱스의 이후 인덱스들을 뒤로 밀거나 앞으로 당기는 것)이 더 오래 걸리기 때문이다.
ArrayList가 해당 인덱스에 접근하는 시간복잡도 O(1)을 무마시킬 만큼 인덱스 사이의 데이터 추가, 삭제 시에 일어나는 연산의 속도가 굉장히 느리다는 것이다.

 

 

결론

드디어 get() 메서드 존재 이유에 대한 궁금증이 풀렸다.

또한 위와 같은 이유로 LinkedList가 ArrayList에 비해 조회에 더 느리고, 수정, 삭제가 용이하다는 것을 이론적으로만 알고 있었는데, 공부를 하고 나니 더 깊게 알게 되었다.

이러한 점들을 고려하여 코딩테스트 또는 개발 시에 알맞은 자료구조를 사용해야겠다는 생각이 들었다.