[자료구조] ArrayList와 LinkedList정리 (Java)

자바 컬렉션 프레임워크(JCF)

JAVA에서는 다양한 자료구조가 JCF (Java Collection Framework)라는 프레임워크로 제공된다.

 

JCF는 크게 두가지로 분류된다.

 

1. 순서나 집합적인 공간을 사용하는 Collection

2. Key와 Value로 데이터를 다루는 Map

JCF 상속구조

 

오늘 알아볼 자료구조는 Collection에 속해있는 LinkedList와 ArrayList이다. 

 

ArrayList

ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일 것이다. 이 ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.

 

ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다. 예를 들면, 첫 번째로 저장한 객체는 Object배열의 0번째 위치에 저장되고 그 다음에 저장하는 객체는 1번째 위치에 저장된다. 이런 식으로 계속 배열에 순서대로 저장되며, 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음 저장된다.

 

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

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

 

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

LinkedList

다음 JCF 계층구조를 보면 LinkedList는 ArrayList와는 달리 List 인터페이스로 구현한 AbstractList를 상속하지 않고 AbstractSequentialList를 상속하고 있다.

 

JCF 계층구조

 

 

 

ArrayList와 LinkeLIst는 메모리 사용방식에 차이가 있다.

 

ArrayList는 데이터들이 순서대로 쭉 늘어선 배열의 형식을 취하고 있는 반면 LinkedList는 순서대로 늘어선 것이 아니라 자료의 주소 값으로 서로 연결되어 있는 구조를 가지고 있다.

 

ArrayList/ LinkedList 데이터 저장방식

 

위의 그림에서 알 수 있듯이 LinkedList의 각 요소들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

 

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

 

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

 

 

 

내용 정리

위에서 말한 ArrayList와 LinkedList를 비교 정리하면 다음과 같다.

 

데이터 삽입/ 삭제

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

ArrayList 

ArrayList는 Size가 고정되어 있기 때문에 삽입 시 사이즈를 늘려주는 연산이 추가되어야한다. 그리고 삭제 시에는 순차적으로 저장되어있는 데이터 구조로 인해 삭제된 부분을 채워야하므로 연산이 또 추가된다. 이러한 부가적인 연산들이 시스템의 성능 저하로 이어져 실제로 ArrayList에서는 데이터 삽입/삭제 효율이 매우 낮아 잘 사용하지 않는다.

 

하지만 LinkedList는 이러한 문제를 연결 형태로 해결하였다. 

LinkedList 

LinkedList 데이터(Node)의 구조는 Data Field와 Link Field로 나뉘어져있다. Data Field에는 데이터 값이 들어가고 Link Field에는 포인터나 참조값을 저장해서 노드와 노드를 연결시키는 방법을 사용한다. 

• Head : LinkedList의 맨 앞부분으로 건물로 비유하면 출입문과 같은 역할을 한다.

 

데이터 탐색

ArrayList는 Random Access 임의 접근 방식이 가능하지만,  LinkedList는 Head에서부터 Sequential Access 순차 접근 방식으로 데이터를 탐색해야 한다.

 

ArrayList 

ArrayList는 데이터들을 연속적인 묶음으로 묶어 자료를 저장하여 탐색하는 방식으로 사용하기는 매우 적절하다.

 

LinkedList 

그러나 단순 LinkedList는 데이터 흐름은 단방향성이고, 데이터들을 불연속적인 단위로 저장하기 때문에 메모리 이곳저곳에 산재해 저장되어 접근하는데에 ArrayList보다 시간이 오래걸린다. 그리고 Link Field의 메모리를 추가적으로 할당해야하는 부분도 고려해야한다.

 

 

단방향 연결리스트 탐색방식

 

표로 정리하면 다음과 같다.

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

 

시간복잡도 비교

	ArrayList	LinkedList
탐색	O(1)	O(1)
맨 뒤 데이터 추가/ 삭제	O(1) or O(n)	O(1)
맨 뒤 이외의 위치에 데이터 추가/삭제	O(n)	O(1)
임의 위치 데이터 탐색	O(1)	O(n)
크기 구하기	O(n)	O(1) or O(n)

 

그래서 실제로 LinkedList의 탐색 성능에 대한 단점을 보완하고자 Double LinkedList 방식을 많이 사용한다.

 

Double LinkedList는 앞뒤로 탐색이 가능하므로 탐색 방향을 능동적으로 정할 수 있어서 LinkedList의 단점을 상쇄시킬 수 있다. 그러나 공짜는 아니다. Link Field를 하나 더 할당해줘야해서 메모리를 더 많이 사용하고 구현이 조금 더 복잡해지는 단점을 갖게된다.

 

 

이중 연결리스트 탐색방식

 

Double LinkedList의 접근성을 보다 향상시킨 것이 Double Circular LinkedList이다. 단순히 Double LinkedList의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 이렇게 하면, 마지막 요소의 다음요소가 첫번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다. 마치 TV의 마지막 채널에서 증가시키면 첫 번째 채널로 이동하고 첫 번째에서 감소시키면 마지막 채널로 이동하는 것과 같다.

 

 

---

Java로 LinkedList구현하기 예제보러가기

[Java/ 4주차 과제 #2] LinkedList 구현하기