[Java] LinkedList 사용법 with Java
🎯 LinkedList 란 ?
LinkedList는 노드(객체) 들이 연결된 형태의 자료 구조 입니다. 예를들어 사람 줄을 세우는데 첫번째 사람의 정보에 그 다음 사람이 어디 있는 지를 표시해 놓은 방법입니다.
ArrayList 와는 차이점이 있는데, 내부적으로 배열을 이용해 조작이 가능한 자료구조가 ArrayList 라면 LinkedList 는 노드끼리의 포인터를 서로 가리키며 참조하게 만들어진 구조 입니다.
즉, 각각의 노드(객체)에는 다음 노드가 어디 있는지를 포함하고 있는 연결 형태의 자료구조 입니다.
LinkedList 와 ArrayList 의 차이점을 정리해보면 다음과 같습니다.
| 특징 | ArrayList | LinkedList |
| 구조 | 동적 배열 | 이중 연결 리스트 |
| 인덱스 접근 속도 | 빠름 O(1) | 느림 O(n) |
| 삽입/삭제 속도 | 느림 O(n) | 빠름 O(1) |
| 메모리 효율성 | 효율적 | 추가 참조로 인해 비효율적 |
이러한 차이점을 인지하고 Linked 리스트는 요소를 자주 삽입하거나 삭제할때 사용하는것이 유리 합니다. 그러나 인덱스 기반의 접근이 많거나 메모리 효율성이 중요한 경우 ArrayList가 더 적합합니다.
🎯 LinkedList 사용법
배열은 모든 데이터가 연속적으로 존재하지만, LinkedList 는 불연속적으로 존재하는 데이터를 연결한 형태로 구성되어 있습니다.
✅ LinkedList 선언방법
LinkedList<E> linkedList = new LinkedList<>();
✅ LinkedList 삭제 과정
삭제하려는 노드의 이전 노드 의 참조값을 변경합니다. 즉, 단 하나의 참조만 변경하면 삭제가 이뤄지는 것입니다. 배열(ArrayList) 은 데이터를 삭제할때 모든 데이터를 복사하는 과정이 있기 때문에 LinkedList 가 배열보다 더 빠른 속도로 값을 삭제 할 수 있습니다.
✅ LinkedList 데이터 추가 과정
추가할 노드를 생성하고, 추가하고자 하는 이전 노드의 참조를 변경합니다. 그리고 새로운 노드가 다음으로 연결할 노드의 참조값을 갖도록 합니다. 이러한 과정 역시 배열 보다 더 빠른 속도로 값을 추가할 수 있는 이유입니다.
🎯 Doubly LinkedList (이중 연결 리스트)
링크드 리스트는 이동 방향이 단방이므로 이전 요소에 대한 접근이 어렵습니다. 이러한 단점을 보완하고자 나온 개념이 바로 이중 연결 리스트 입니다.
이중 연결 리스트는 기존의 링크드 리스트 노드에 이전 노드에 대한 참조를 추가한 자료 구조입니다. 이렇게 구현된 이중 연결리스트는 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트 보다 더 많이 사용됩니다