Java - LinkedList (feat. vs ArrayList)

<출처> 자바의 정석에 나온 내용

 

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

 

1. 크기를 변경할 수 없다.
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다.
- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리 낭비가된다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 
- 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터를 복사해서 이동해야 한다.

 

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

 

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

 

링크드 리스트에서의 데이터의 삭제는 간단하다. 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 단 하나의 참조만 변경하면 삭제가 이루어진느 것이다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

 

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

 

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

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

 

더블 링크드 리스트는 링크드 리스트 보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트 보다 더 많이 사용된다. 

 

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 '더블 써큘러 링크드 리스트(이중 원형 연결 리스트) 인데, 단순히 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 이렇게 하면, 마지막 요소의 다음 요소가 첫번째 요소가 되고, 첫번째 요소의 이전 요소가 마지막 요소간 된다. 마치 TV의 마지막 채널에서 채널을 증가 시키면 첫번째 채널로 이동하고 첫번째 채널을 감소시키면 마지막 채널로 이동하는 것과 같다.

 

실제로 LinkedList 클래스는 이름과 달리 '링크드 리스트'가 아닌 '더블 링크드 리스트'로 구현되어 있는데, 이는 링크드 리스트의 단점인 낮은 접근성을 높이기 위해 한 것이다. 

 

 

ArrayList vs LinkedList

 

 ArrayList LinkedList 둘다 List 인터페이스를 구현했기 때문에 ArrayList 와 내부구현방법만 다를뿐 제공하는 메서드의 종류와 기능은 거의 같다. 

 대신 두 가지의 List 성능차이를 비교하고 그 결과를 설명할 줄 알면 된다. 

 

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

  단순히 저장하는 시간만을 비교할 수 있도록 하기 위해서는 ArrayList를 생성할 때는 저장할 데이터의 개수 만큼 충분한 초기용량을 확보해서 진행하게 되어있을때, 저장공간이 부족하여 배열의 복사를 하게 되는 경우를 제외한다면 ArrayList 가 더 빠른 성능을 나타낸다.

 

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

 중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈공간을 채워야하기 때문에 처리 속도가 느리다. 

 

 

따라서 상황에 맞는 자료 구조를 사용하는 것이 중요하다. 

 

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

 

다루고자 하는 데이터 개수가 변하지 않는 경우라면, ArrayList 가 최상의 선택이 되겠지만, 데이터 개수의 변경이 잦다면 LinkedList 를 사용 하는 것이 더 나은 선택이 될 것이다.

 

처음에 작업하기전에 데이터를 저장할 때는 ArrayList 를 사용한 다음, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 더 좋은 효율을 얻을 수 있을 것이다.

 

컬렉션 프레임웩에 속한 대부분의 컬렉션 클래스들은 이처럼 서로 변환이 가능한 생성자를 만들어 제공하므로 이를 잘 활용해보자.