[자바의 정석] 11. 컬렉션 프레임웍 - LinkedList

1.3 LinkedList

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근시간, access time)이 가장 빠르다는 장점을 가지고 있다.

 

단점

1. 크기를 변경할 수 없다.

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

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

• 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
• 배열의 중간에 데이터를 추가하면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

 

이러한 배열의 단범을 보완하기 위해 링크드 리스트(linked list)라는 자료구조가 고안되었다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.

 

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

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

링크드 리스트에서 데이터 삭제는 간단하다.삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 단 하나의 참조만 변경하면 삭제가 이루어지는 것이다.

 

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

 

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

 

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

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

 

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 ‘더블 서큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list)’인데, 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다.

 

 

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

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

결론3 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 접근시간이 길어진다.

 

 

배열의 경우 만일 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래의 식으로 계산

인덱스가 n인 데이터의 주소 + 배열의 주소 + n(번째 요소) * 데이터 타입의 크기

 

다루고자 하는 데이터의 개수가 변하지 않는다 - ArryaList

데이터 개수의 변경이 찾다 - LinkedList

 

 

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

ArrayList al = new ArrayList(1000000);
for(int i=0; i<1000000; i++) al.add(i+"")

LinkedList ll = new LinkedList(al);
for(int i=0; i<1000; i++) ll.add(500, "X") //500위치에 "x"추가

 

 

 

 

출처 : 남궁성. 「자바의 정석」. 도우출판. 2016