Collection Framework 정복 3탄 - LinkedList
LinkedList
자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 및 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있습니다. ArrayList는 내부적으로 배열을 이용하여 메서드로 이리저리 조작이 가능하게 만든 메서드라면, LinkedList는 노드(객체)끼리 주소 포인터를 서로 가리켜 이어지는 구조입니다.
위 그림을 보면 LinkedList는 각 노드가 화살표로 연결되어 있는 것을 볼 수 있습니다. 이러한 노드들은 하나의 객체라고 이해하시면 됩니다.
이해를 좀더 돕기 위해 밑의 코드를 보겠습니다!
class Node{
Node next; // 다음 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
}위 경우는 단방향 연결 리스트의 Node를 나타냅니다. 현재 노드의 경우에는 다음 노드 주소를 저장하는 필드만이 존재합니다. 그렇다면 만약 1000번째 노드에 접근하려면 어떤 상황이 발생할까요?? 처음 노드부터 next를 1000번 타고 들어가야 해당 Node를 조회할 수 있을 것입니다. 이러한 상황에 대비해 자바는 여러 종류의 링크드 리스트를 제공하는데 이것들에 대해 알아보겠습니다.
LinkedList 종류
단방향 연결 리스트
위에서 말씀드렸듯이, 다음 노드를 가리키기 위한 포인터 필드 next만을 가지고 있는 링크드 리스트를 단방향 연결 리스트(singly linked List)라고 합니다.
단방향 연결리스트의 구조를 보고있으면, 어...? 그러면 특정 노드에서 이전 노드에 접근하려면 어떡해야 하지??라는 의문점이 드실 수 있는데, 이러한 단점들을 극복하기 위해 나온 자료구조가 Doubly Linked List입니다.
양방향 연결 리스트
class Node{
Node next; // 다음 노드를 가리키기 위한 필드
Node prev; // 이전 노드를 가리키기 위한 필드
int data; // 데이터를 저장하는 필드
}위 코드와 그림을 보면 이해하실수 있듯이 단일 연결 리스트의 노드와 다르게 이전 노드를 가리키는 필드 또한 존재합니다.
단일 연결리스트에서 특정 노드를 조회할 때 되게 불편했던 것 기억하시나요?? 이와 다르게 양방향 연결 리스트는 이전 노드 또한 참고하기에 각 요소에 대한 접근 및 이동이 쉽습니다.
또한 Java Collection Framework에 구현된 LinkedList는 doubly Linked List로 구성되어 있습니다!
양방향 원형 연결 리스트
양방향 원형 연결 리스트는 양방향 연결리스트와 다르게 첫번째 노드와 마지막 노드를 각각 연결시켜 원형으로 만들었다는 점만 기억하시면 됩니다!
LinkedList vs ArrayList 특징 비교
위 표를 통해 두 자료구조에 대해 이해도를 높여 보겠습니다.
우선 왜 데이터 접근 시간에서 왜 차이가 나는걸까요?? 개발자 입장에서는 두 자료구조 다 인덱스를 통해 접근이 가능합니다. 하지만 내부에서 해당 값을 찾는 방식이 다릅니다.
ArrayList의 경우엔 내부에 Object []를 가지고 있으며, 이에 따라 인덱스를 바탕으로 해당 데이터에 직접 접근할 수 있는 Random Access가 가능합니다. 하지만 LinkedList의 경우엔 보통 첫 번째 노드와 마지막 노드의 참조를 가지고 있고, 이를 바탕으로 순차적으로 접근해야 하기에 탐색 시간이 오래걸립니다.
또한 두 자료구조 삽입/삭제 시간은 상황에 따라 다를 수 있습니다. 예를 들어 맨 마지막에 있는 데이터를 지운다고 생각해 보겠습니다. 이때는 ArrayList 또한 값을 제거할 때 나머지 값들을 이동할 필요가 없습니다. 하지만 중간에 있는 데이터를 지운다고 생각해 보면 둘의 차이점을 명확히 이해할 수 있습니다.
중간의 값을 지울 때 LinkedList는 마지막 값을 지울 때와 다르지 않게 삭제 대상 노드의 바로 앞에 있는 노드의 next 포인터가 삭제 대상 노드의 바로 뒤에 있는 노드를 가리키게만 하면 됩니다.(물론 단방향 연결리스트의 경우입니다)
하지만 ArrayList의 경우에는 중간의 값을 삭제하게 되면, 빈 값을 둘 수 없다는 자료구조의 특성상 중간 값 뒤에 있는 모든 값들을 앞으로 한쪽씩 옮겨야 하므로 최악의 경우 O(n)의 연산속도를 보입니다.
또한 CPU Cache라는 부분을 보면 ArrayList는 cache의 이점을 사용하지만, LinkedList에는 별말이 없습니다.
이에 대한 내용을 지금 이 글에서 다루기엔 너무 길어질 수 있어서 이해하시고자 하는 분들께 힌트를 드리자면 CPU가 RAM에서 데이터를 읽어온 후 Cache에 값을 어떻게 저장하는지, 공간 지역성이 무엇인지, Cache Hit이 무엇인지 총 3가지 개념에 대해 공부를 해보시면 위의 내용을 이해하실 수 있을 겁니다!
단일 연결 리스트 시간복잡도 정리
보통 링크드 리스트의 삽입 삭제의 O(1)의 시간복잡도를 가진다고 많이들 외우고 계실 겁니다! 저도 이 글을 작성하기 전에 그랬습니다.
하지만 엥?? 왜 삭제가 무조건 O(1)이지??라는 의문점을 가지고 이에 대해 찾아보니 LinkedList는 내부적으로 head 노드와 tail 노드의 참조값을 가지고 있기에 이와 관련된 삽입이나 삭제 시에는 O(1)이 맞습니다.
하지만 만약 중간에 노드를 삭제하거나 삽입하려면 어떡해야 할까요?? 이 경우엔 우선 그 노드까지 접근을 한 다음 해당 연산을 진행해야 합니다.
즉 head, tail노드와 관련 없는 노드를 삭제할 경우 최악의 경우 O(n+1)의 시간복잡도를 가집니다.
참고
이글을 바탕으로 LinkedList에 대해 어느정도 이해가 되셨으면 좋겠습니다 ^^
혹시 틀린 사항이 있다면 언제든지 지적해주시면 감사하겠습니다.
https://inpa.tistory.com/entry/JAVA-☕-LinkedList-구조-사용법-완벽-정복하기#