AVA - 컬렉션 프레임웍(Collections Framework) (3)

LinkedList

배열은 다음과 같은 단점이 존재한다.

1. 크기를 변경할 수 없다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

이를 보완하기 위해서 LinkedList가 등장했다. 링크드 리스트는 불연속적으로 존재하는 데이터를 서료 연결한 형태로 구성되어 있다.

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

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

링크드 리스트에서 데이터를 삭제하고자 하는 경우, 삭제할 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다.

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

새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 된다. 따라서 처리속도가 매우 빠르다.

링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이 점을 보완한 것이 더블 링크드 리스트이다.

더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조 뿐만 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.

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

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 '더블 써큘러 링크드 리스트'이다.
이는 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 연결시킨 것이다.

마지막요소의 다음요소가 첫번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다.

결론
1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 이처럼 간단히 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만

LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다.

그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어 오는 시간이 길어진다는 단점이 있다.

다루고자 하는 데이터의 개수가 변하지 않는 경우라면 ArrayList를

데이터의 개수 벼경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이라고 할 수 있겠다.