Array, LinkedList, ArrayList의 차이점

서론 

안녕하세요. is낫널입니다.

정말 오랜만에 글을 쓰러 왔네요..

CS 스터디를 저번주부터 참여하지 않게 되면서 첫 이력서를 제출하였습니다. 

이제 이력서를 넣으면서 제대로 된 취준을 시작한 지 일주일 째인데 벌써 학원 수료한 지는 3개월이 되어가네요. 

하루하루를 헛되이 보내지 않게 노력했던 것 같지만, 뒤돌아보니 별로 남은 게 없어서 불안한 마음이 들기도 하는 날입니다. 

그래서 이렇게 기록이 남는 블로그를 찾게 되었네요. 

CS 스터디는 참여하지 않지만, 꾸준한 CS 공부를 하겠다고 다짐했었는데 그것을 이뤄내보겠습니다. 

오늘도 읽으러 와주신 분들께 감사의 말씀을 전합니다. 

 

 

본론 

 

Array(배열) 이란? 

인덱스와 값의 쌍으로 이루어진 연속적인 메모리의 집합입니다. 

이 때 인덱스(Index)는 어떤 값에 접근하기 위해 필요한 것입니다. 

값(Value)은 배열 안에 실제로 들어가 있는 값을 의미합니다. 

배열이 선언되면 컴파일러는 배열의 크기만큼 연속적인 공간을 메모리에 할당합니다. 

그래서 연속적인 공간이기 때문에 인덱스를 통해 메모리 접근이 가능한 것입니다. 

 

배열의 장점

배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time) 이 짧습니다. 

그래서 값에 접근할 때 O(1) 의 시간 복잡도로 어떤 값에 접근하든지 모두 동일한 시간이 걸립니다. 

 

 

배열의 단점

그러나 이런 배열에게도 단점이 존재합니다. 

첫 번째, 크기를 실행 중에 변경할 수 없습니다. 
실행 중이 아니더라도, 크기를 변경해야 하는 과정이 생각보다 오래 걸립니다. 

해당 과정을 살펴보자면, 

1. 기존 배열보다 크기가 더 큰 배열을 생성합니다. 
2. 기존 배열에 담긴 값들을 새로 생성한 배열에 복사해 줍니다.
3. 기존 배열을 참조하던 주소를 새로운 배열을 참조할 수 있게 변경해 줍니다. 

이렇게 총 3가지의 과정을 거치므로 시간이 오래 걸린다는 것을 알 수 있습니다.

이러한 크기 변경을 피하는 방법도 있지만, 크기 변경을 피하기 위해서 충분히 큰 배열을 생성하게 된다면

메모리가 낭비되는 문제도 발생하게 됩니다.

 

두 번째, 비순차적인 데이터의 추가, 삭제에 시간이 오래 걸립니다. 

비순차적이라는 의미는 배열의 순서대로 인덱스 맨 마지막에 값이 추가되거나, 인덱스 맨 마지막의 값이 삭제되는 것이 아닌 

인덱스 중간의 어떤 지점에서 데이터의 추가, 삭제가 이뤄지면 시간이 오래 걸린다는 의미입니다. 

이유는 데이터를 추가하게 될 경우, 뒤의 데이터를 뒤로 옮기는 과정이 발생하고 

데이터를 삭제하게 될 경우, 뒤의 데이터를 앞으로 옮기는 과정이 발생하면서 시간이 지체되기 때문입니다.

그래서 반대로 순차적인 데이터의 추가나 삭제는 시간이 지체되지 않고 빨리 처리된다는 것을 알 수 있습니다. 

 

 

이제 이러한 Array(배열)의 단점을 보완한 자료구조가 LinkedList입니다.

 

 

 

LinkedList(연결리스트) 란?

LinkedList는 배열과 달리 불연속적으로 존재하는 데이터를 서로 연결(link) 한 형태로 구성되어 있습니다. 

출처 : https://inpa.tistory.com/entry/JAVA-☕-LinkedList-구조-사용법-완벽-정복하기

위의 그림을 확인해 보면, 배열과 달리 LinkedList 가 갖고 있는 각 요소인 빨간색 박스를 Node라고 부릅니다. 

Node는 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있습니다. 

코드로 구성해 보자면, 아래와 같습니다. 

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

 

 

LinkedList의 장점

연결리스트의 장점으로 첫 번째는, 데이터의 삭제는 단 한 번의 참조 변경만으로 가능하다는 것입니다.

즉, 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 되는 것입니다.

만약, 위의 사진으로 예를 든다면 0x200에 위치한 요소가 다음 요소인 0x300를 참조하다가, 0x300이 삭제된다면 0x300을 가리키던 주소만 다음 요소를 가리키는 0x350으로 참조변경만 하면 됩니다. 

그래서 배열처럼, 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 배열에 비해 처리속도가 빠른 것입니다.

 

두 번째로, 데이터의 추가는 한 번의 Node 객체 생성과 2번의 참조변경만으로 가능합니다. 

이것도 첫 번째 말과 사실 비슷하지만 참조변경을 한번 더 한다는 것이 다릅니다.

그래도 풀어서 설명하자면, 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해 주고, 새로운 요소가 그다음 요소를 참조하도록 변경하기만 하면 된다는 의미입니다.

이것도 예시를 들자면, 0x350과 0x380 요소 사이에 새로운 요소인 0x360이 추가된다고 가정했을 때 새로운 요소를 위한 객체 생성을 한 다음 이전 요소인 0x350가 새로운 요소인 0x360을 참조하도록 변경해 주고, 0x360이 그다음 요소인 0x380 요소를 참조하도록 변경해주기만 하면 됩니다. 

이것도 역시, 배열에 비해 처리속도가 빠릅니다.

 

 

LinkedList의 단점

하지만, 이러한 연결 리스트도 단점은 존재합니다.

그것은 바로 접근성이 나쁘다는 것입니다.

왜냐하면,

LinkedList는 위의 사진을 확인했을 때도

이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전요소에 대한 접근은 어렵기 때문입니다. 

하지만 그에 비해, 배열은 인덱스를 통해 한번에 해당 인덱스번호로 이동이 가능합니다. 

그래서, 연결리스트는 단방향이기 때문에 하나하나 해당 요소로 접근해야 합니다.

이러한 이유로 처리속도가 느린 것이 단점입니다. 

 

 

 

Doubly Linked List(이중 연결 리스트)

또한, LinkedList의 접근성이 나쁜 단점을 보완하기 위해 나온 자료구조가 Doubly Linked List입니다. 

이중연결리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했으며, 이를 제외하면 링크드 리스트와 같습니다. 

 

조금 시각적으로 확인해 보기 위해서 사진을 첨부합니다. 

출처 : https://inpa.tistory.com/entry/JAVA-☕-LinkedList-구조-사용법-완벽-정복하기

코드를 확인했을 때, 연결리스트와 다른 것은 이전 요소의 주소를 담을 수 있는 변수가 생겼다는 것입니다. 

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

 

 

 

 

Doubly Circular Linked List(이중 원형 연결 리스트)

이제 doubly linked list에서 바로 위의 사진에서 확인했듯이 참조의 끝은 null 인 것을 확인할 수 있습니다.

이러한 점을 이용하여 이중연결리스트보다 더 접근성이 개선된 자료구조가 doubly circular linked list입니다.

이것도 앞서 설명한 링크드 리스트 자료구조들과 다를 바 없이 단순히 이중연결리스트의 첫 번째 요소와 마지막 요소를 서로 연결시켜 만들어진 형태입니다. 

 

출처 : https://inpa.tistory.com/entry/JAVA-☕-LinkedList-구조-사용법-완벽-정복하기

이러한 구조는 티브이 채널을 순회하거나 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용되기도 합니다. 

 

그러나, 이러한 이중 원형 연결리스트는 자주 사용되지 않으며, Java에서는 이중 연결리스트로 구현되어 있습니다. 

 

ArrayList 란? 

이제 마지막으로 ArrayList에 대해 확인해 보자면,

Arraylist는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트입니다. 

 

Array와 Arraylist의 가장 큰 차이점은 배열의 크기가 동적인지, 정적인지입니다. 

 

Array는 한번 생성되면 크기가 변하지 않지만, ArrayList는 객체들이 추가되어 저장용량(capacity)을 초과한다면

자동으로 부족한 크기만큼 저장 용량이 늘어난다는 특징을 가지고 있습니다. 

 

정리하자면, 

Array는 정적인 사이즈의 배열을 생성하고, Arraylist는 동적인 사이즈의 배열을 생성합니다. 

그 외에는 Array와 동일합니다. 

 

 

여기서 이제 가장 중요한 것은 LinkedList와 ArrayList의 차이점입니다. 

LinkedList vs ArrayList 

1. [컬렉션 구성]            LinkedList : 노드로 연결된 자료구조 / Arraylist : 배열을 이용한 자료구조   

2. [데이터 접근시간]    LinkedList : 위치에 따라 이동시간 발생 / Arraylist : 모든 데이터 상수 시간 접근

•   LinkedList는 앞서 설명했듯이, 인덱스가 아닌 다음 노드의 주소값을 참조하는 방식이기 때문에 순차적으로 데이터에 접근합니다. 그러나 ArrayList 는 인덱스를 통해 데이터에 접근하기 때문에, 모든 데이터에 무작위로 접근이 가능합니다. 

3. [삽입/삭제 시간]      LinkedList : 삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생 / Arraylist : 비 순차적인 삽입 /삭제 시 데이터 이동과정으로 추가시간 발생 

• LinkedList 는 삽입/ 삭제 시 참조하는 주소값만 바뀌면 되는 것이기 때문에, 비순차적인 부분에서는 Arraylist 보다 시간이 빠릅니다. 
• 그러나, 순차적인 삽입/ 삭제 일 경우 LinkedList와 ArrayList는 상수 시간을 갖습니다. 

4. [Resizing 필요]    Arraylist : 공간이 부족할 경우 새로운 배열에 복사하는 추가시간 발생 

• Resizing 이란, 크기를 조정한다는 의미로 공간을 생성하여 메모리에 할당하는 Arraylist는 공간이 부족할 때는 리사이징이 필요합니다. 

5. [CPU Cache]    Arraylist : 캐시 이점을 활용

• 배열을 이용한 자료구조인 Arraylist 는 데이터가 메모리 상에 순차적으로 저장되기 때문에 공간 지역성이 좋아 높은 Cache Hit Rate를 가집니다. 
• 공간 지역성이란, 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성입니다.
• Cache Hit Rate 란, 요청할 데이터를 캐시 메모리에서 찾을 확률을 말합니다. 

 

 

 

마무리

이렇게 Array, LinkedList, ArrayList에 대해서 간단하게 알아보았습니다.

끝까지 글을 읽어주셔서 감사합니다. 

잘못된 부분이 있다면 댓글로 알려주시면 감사하겠습니다 :) 

 

 

★ 참고한 링크

Inpa Dev 님의 블로그와 남궁성 강사님의 강의를 참고하였습니다. 

🧱 ArrayList vs LinkedList 특징 & 성능 비교