[JAVA][자료구조] Linked List

목적

자바에서 LinkedList는 데이터를 연결된 노드로 구성된 선형 자료구조입니다.

오늘은 LinkedList에 대해서 알아보겠습니다.

• LinkedList 특징에 대해 알아보자
• LinkedList 관련 메소드에 대해서 알아보자.

Linked List

• 각 노드는 값과 다음 노드에 대한 참조(주소)를 가지고 있습니다.
• 각 요소들이 메모리 상에 임의로 배치되어 있으며, 인덱스 기반으로 접근하는 것이 아닌
  다음 노드를 통해 순차적으로 탐색합니다.
• 삽입 및 삭제 작업이 많을 때 유용한 자료구조입니다.
  중간에 요소를 추가하거나 삭제할 경우, 단순히 앞뒤의 두 개의 포인터만 변경하면 되기 때문에 O(1) 시간 복잡도로 수행됩니다.

• 임의 위치에 접근하기 위해서는 처음부터 순차적으로 탐색해야 하므로 O(n) 시간 복잡도가 소요됩니다.

LinkedList는 자주 사용되는 자료구조 중 하나이며, 다양한 상황에서 유용하게 활용됩니다.

그러나 데이터 접근 시 선형 탐색이 필요하기 때문에 검색 속도가 느릴 수 있으므로,

특히 대량의 데이터를 저장할 경우 ArrayList와 같은 다른 자료구조와 비교해볼 필요가 있습니다.

관련 메서드

1. boolean add(Object element): 리스트의 마지막에 주어진 요소를 추가합니다.
2. void addFirst(Object element): 리스트의 처음에 주어진 요소를 추가합니다.
3. void addLast(Object element): 리스트의 마지막에 주어진 요소를 추가합니다.
4. boolean remove(): 리스트에서 첫 번째 요소를 제거하고 반환합니다.
5. Object removeFirst(): 리스트에서 첫 번째 요소를 제거하고 반환합니다.
6. Object removeLast(): 리스트에서 마지막 요소를 제거하고 반환합니다.
7. Object get(int index): 지정한 인덱스 위치의 요소 값을 반환합니다.
8. Object set(index, element): 지정한 인덱스 위치의 값을 변경합니다.

노트 정리