[Java] 컬렉션 프레임윅 (LinkedList)

• 배열

• LinkedList

• doubly linked list (이중 연결리스트)

• doubly circular linked list (이중 원형 연결리스트)

• 결론

배열

 - 장점 : 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠름

 

 - 단점 

1. 크기를 변경할 수 없다.
 - 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 한다.
 - 실행속도 향상을 위해 충분히 큰 크기의 배열을 생성해야 하므로 메모리 낭비 발생

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
 - 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
 - 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 함.

 

LinkedList

 

: 배열은 모든 데이터가 연속적이지만, 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태

 

링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성됨

class Node {
    Node next;  // 다음 요소의 주소를 저장
    Object obj;  // 데이터를 저장
}

 ▶ 단 하나의 참조만 변경하면 삭제가 이뤄짐.

 

 

doubly linked list (이중 연결리스트)

 

: 링크드 리스트는 이동방향이 단방향이기 때문에 이전요소에 대한 접근이 어렵다.

: 더블 링크드 리스트는 참조변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능

 

★ LinkedList클래스는 '더블 링크드 리스트'로 구현되어 있음.

 

class Node {
    Node next;  // 다음 요소의 주소를 저장
    Node previous;  // 이전 요소의 주소를 저장
    Object obj;  // 데이터를 저장
}

 

 

doubly circular linked list (이중 원형 연결리스트)

 

: 첫 번째 요소와 마지막 요소를 서로 연결시킨 것

 

 

 

 

결론

 

1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.

 

2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

 

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

▶ LinkedList에서는 사용 불가.(불연속적으로 위치했기 때문에)

 

컬렉션	읽기(접근시간)	추가 / 삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

▶ 컬렉션 프레임웍에 속한 대부분의 컬렉션 클래스들은 이처럼 서로 변환이 가능한 생성자를 제공하므로 

     원하는 상황에 맞게 취사선택 할 수 있어야 함.