#12. 배열(Array)과 연결 리스트(LinkedList)

출처 :  Array vs. Linked List - HappyCoders.eu

이번 주는 기술 면접에서 많이 물어본다는 Array와 LinkedList의 특징과 차이점에 대해 정리해보았다. 같은 선형 자료구조이면서 정적 자료구조(Array)와 동적 자료구조(LinkedList)로 나뉘어서 자주 나오는 질문이 아닐까 싶다!

Array

배열(Array)은 메모리 상에 원소를 연속하게 배치한 자료구조이다. 특징을 간단히 정리하자면 다음과 같다.

• 인덱스를 사용해 값에 바로 접근 가능하다.
• 배열의 크기는 한 번 선언하면 줄이거나 늘릴수 없다. (따라서 배열을 확장하기 위해서는 기존 배열의 내용을 새로운 배열에 복사하는 식으로 확장해야한다.)
• 새로운 값을 삽입하거나 삭제하기가 비효적이고 어렵다. (임의의 위치에 있는 원소를 추가/제거하는 시간 복잡도 O(N))
• 데이터를 조회하는 연산이 많을 때 유용하다. (k번째 원소에 접근하는 시간 복잡도 O(1))

LinkedList

연결 리스트(LinkedList)는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다. 특징을 간단히 정리하자면 다음과 같다.

• 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. (따라서 값에 접근하는 속도가 느리다. k번째 원소에 접근하는 시간 복잡도 O(k))
• 선언할 때 배열처럼 크기를 미리 정하지 않아도 된다.
• 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다. (임의의 위치에 있는 원소를 추가/제거하는 시간 복잡도 O(1))

한 줄 정리 : 크기가 픽스되어있거나 데이터에 접근하는 경우가 많을 때는 배열을 사용, 크기가 변하는 데이터를 다루거나 데이터의 삽입과 삭제가 많은 경우에는 연결 리스트를 사용!

Array vs LinkedList 요약

Array	LinkedList
사이즈가 고정되어있음.	사이즈가 고정되어있지 않음.
데이터의 삽입/삭제가 비효율적. 삽입/삭제가 될 때마다 요소들이 계속 이동함.	데이터의 삽입/삭제가 효율적. 삽입/삭제가 요소들의 이동 없이 가능함.
인덱스를 이용해 값에 효율적으로 접근 가능함.	인덱스가 없으므로 인덱스를 이용해 값에 접근 불가능.
배열을 꽉 채워서 사용하지 않을 시 메모리 낭비가 될 수 있음.	메모리가 동적으로 할당되기 때문에 메모리 낭비X
순차적인 접근이 빠름.(요소들이 서로 인접해있으므로)	순차적인 접근이 느림.

 

Array vs. Linked List - HappyCoders.eu

What is a Linked List? Linked List vs Array | by YOON MI KIM | Medium

BaaaaaaaarkingDog | [실전 알고리즘] 0x04강 - 연결 리스트 (encrypted.gg)

🧱 자바 LinkedList 구조 & 사용법 - 정복하기 (tistory.com)