[자료구조] 자바 LinkedList(연결리스트)?

LinkedList란 말그대로 각 노드들이 한줄로 연결되어있는 구조리스트(자료의 주소값으로 서로 연결되어있는 구조)를 말한다.

여기서 노드들은 데이터와 포인터를 가지고 있는데, 이때 노드의 포인터가 이전노드와 다음 노드와의 연결을 담당한다.

 

중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다.

 

그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다.

LinkedList를 그림으로 나타내면 아래와 같다.(파란색 부분이 포인터, 하늘색 부분이 데이터를 나타냄)

---

여기서 LinkedList와 ArrayList의 시간 복잡도를 비교해보자.

특정요소에 접근(탐색) 부분에서는 ArrayList가 O(1)로 유리하고

삽입/삭제 부분에서는 LinkedList가 맨앞 에서는 O(1)로 유리하지만, 맨앞 그 이후라면, O(n)의 시간복잡도를 가진다.