Chapter 11) 컬렉션 프레임워크 - LinkedList

◇ LinkedList?

불연속적으로 존재하는 데이터를 서로 연결(link)한 형태)

 

기존 배열의 단점은 다음과 같다.

• 크기 변경 불가
• 비순차적 데이터 추가 및 삭제 시간 오래 소요.

이 단점을 보완하기 위해 LinkedList라는 자료구조가 고안되었다.

아래 코드를 보면 알다시피 LinkedList의 각 요소들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

class Node{
    Node next;
    Object obj;
}

LinkedList에서의 데이터 삭제는 다음과 같이 이루어진다.

• 삭제하고자하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다
• 끝!

배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

 

LinkedList에서의 데이터 추가는 다음과 같이 이루어진다.

• 새로운 요소(Node)를 생성한 다음 추가하고자하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경하고,
• 새로운 요소가 그 다음 요소를 참조하도록 변경한다.
• 끝!

이것 역시 처리 속도가 매우 빠르다.

◇ LinkedList의 단점?

이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.

=> 이 점을 보완한 것이 Doubly Linked List(이중 연결 리스트)!

각 요소에 대한 접근과 이동이 LinkedList보다 쉽기 때문에 DoublyLinkedList가 더 많이 사용됨.

 

DoublyLinkedList보다 접근성을 더 향상 시킨 것은 Doubly Circular Lnked List(이중 원형 연결 리스트)!

DoublyLinkedList의 첫 요소와 마지막 요소를 서로 연결시킨 것.

 

실제로 LinkedList 클래스는 DoublyLinkedList로 구현되어있다.

◇ LinkedList과 ArrayList의 비교?

• 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
• 데이터를 찾는 경우
  • 배열의 경우 인덱스가 n인 요소의 값을 얻어오고자한다면 단순히 아래와 같은 수식을 계산함으로써 해결
    • 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
  • LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터에 접근하는 시간이 길어진다.

◇ 결론

• 데이터의 개수가 변하지 않는 경우라면 ArrayList가 최상의 선택.
• 데이터의 개수가 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택