[Java Linked List] 자바 링크드 리스트 개념 정리 (feat. 시간복잡도)

자바의 LinkedList 개념📚

 

LinkedList는 자바에서 제공하는 기본적인 자료구조 중 하나로, 데이터를 순차적으로 연결한 형태의 컬렉션입니다. 각 요소(노드)는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있어요.

LinkedList의 기본 구조

• 노드(Node): 데이터를 저장하는 필드와 다음 노드를 가리키는 포인터 필드로 구성됩니다.
• 헤드(Head): 리스트의 가장 앞에 위치한 노드를 가리키는 포인터로, 보통 더미 노드(dummy node)로 사용됩니다. 즉, 실제 데이터를 저장하지 않고 시작점 역할만 합니다.
• 테일(Tail): 리스트의 가장 뒤에 위치한 노드를 가리키는 포인터로, 다음 노드가 없기 때문에 포인터는 null입니다.
  
  

Lineked List 그림 (직접 만듦)

 

LinkedList의 장단점

• 장점: 동적으로 메모리를 할당하기 때문에, 배열과 달리 크기를 미리 지정할 필요가 없습니다. 또한, 중간에 요소를 추가하거나 삭제할 때, 배열에 비해 효율적입니다.
  
  
• 단점: 검색 시, 배열에 비해 성능이 떨어집니다. 배열은 인덱스를 통해 직접 접근이 가능하지만, LinkedList는 항상 처음부터 순차적으로 탐색해야 하기 때문입니다.

 

 

자주 사용되는 LinkedList 메서드

• add(E e): 리스트의 끝에 요소를 추가합니다.
• add(int index, E element): 리스트의 특정 위치에 요소를 추가합니다.
• remove(int index): 리스트에서 특정 위치의 요소를 제거합니다.
• get(int index): 리스트에서 특정 위치의 요소를 반환합니다.
• size(): 리스트의 요소 개수를 반환합니다.
• clear(): 리스트의 모든 요소를 제거합니다.
  
  

 

코드 예시

	// LinkedList 생성
   	LinkedList<String> linkedList = new LinkedList<>();

        // 삽입: 리스트의 끝에 노드 추가
        linkedList.add("사과");
        linkedList.add("바나나");
        linkedList.add("딸기");
        System.out.println(linkedList); // 출력: [사과, 바나나, 딸기]

        // 삽입: 리스트의 시작에 노드 추가
        linkedList.addFirst("포도");
        System.out.println(linkedList); // 출력: [포도, 사과, 바나나, 딸기]

        // 삭제: 리스트의 끝 노드 삭제
        linkedList.removeLast();
        System.out.println(linkedList); // 출력: [포도, 사과, 바나나]

        // 탐색: 특정 인덱스에 있는 노드 찾기
        int index = linkedList.indexOf("사과");
        System.out.println("사과의 인덱스: " + index); // 출력: 사과의 인덱스: 1

 

 

 

 

---

 

 

 

🕒LinkedList의 연산과 시간 복잡도

• 삽입(Insertion):
  • 시작 지점에 노드를 삽입하는 경우: O(1)
  • 중간 또는 끝 지점에 노드를 삽입하는 경우: O(1) + O(n) = O(n) (탐색 후 삽입)
• 삭제(Deletion):
  • 시작 지점의 노드를 삭제하는 경우: O(1)
  • 중간 또는 끝 지점의 노드를 삭제하는 경우: O(1) + O(n) = O(n) (탐색 후 삭제)
•  탐색(Searching):
  • O(n) (전체 리스트를 순회하여 탐색해야 함)