[자료구조] Array, Array List, Linked List

배열(Array)

 

배열은 메모리 상에서 연속적 데이터를 저장합니다. 또한, 인덱스와 번호에 대응하는 데이터로 이루어져 있습니다.

배열에는 데이터들이 순차적으로 저장되어 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있습니다.

첫 번째 값의 인덱스는 0으로 시작하고 마지막 값은 배열의 길이 - 1까지의 인덱스 번호로 되어 있습니다.

 

---

 

Array List

 

배열과 같은 순차리스트이며 인덱스를 내부의 객체를 관리한다는 점은 유사합니다.

하지만 한번 생성되면 크기가 변하지 않는 배열(Array)와 달리

ArrayList는 객체들이 추가되어 저장 용량을 초과한다면 자동으로 부족한 크기만큼 저장 용량이 늘어납니다.

 

---

 

연결 리스트(Linked List)

 

연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조를 말합니다.

포인터를 사용해 연결하며, 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성됩니다.

 

Q. 왜 Linked List를 사용하나?

A. 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있습니다.

1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 합니다.
2. 새로운 요소를 삽입하는 것은 비용이 많이 듭니다. (공간을 만들고, 기존 요소 전부 이동)

 

Linked List 장점

1. 동적 크기
2. 삽입과 삭제가 용이하다.

 

Linked List 단점

1. 임의로 액세스를 허용할 수 없습니다. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야 합니다.
(이진 검색 수행 불가능)
2. 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요합니다.

 

 

---

 

 

---

Array vs ArrayList vs LinkedList

 

 

 

 

• Array는 index로 빠르게 값을 찾는 것이 가능합니다.
• LinkedList는 데이터의 삽입 및 삭제가 빠릅니다.
• ArrayList는 데이터를 찾는 것은 빠르지만, 삽입 및 삭제가 느립니다.

 

---

 

Array vs Linked List

 

Array는 메모리 상에서 연속적인 데이터를 저장합니다.

반면, Linked List는 메모리상에서는 연속적이지 않지만 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로서 논리적 연속성을 유지합니다.

 

시간 복잡도에도 차이가 있습니다.

 

Array는 O(1), Linked List는 O(n)의 시간 복잡도를 가집니다.

삽입 및 삭제의 경우 Array는 O(n), Linked List는 O(1)의 시간 복잡도를 가집니다.

 

 

Q. 어느 상황에 Linked List를 쓰는 것이 Array보다 좋은가?

A. 첫 번째, O(1)으로 삽입/삭제를 자주 해야 할 때
두 번째, 얼마만큼의 데이터가 들어올 지 예측하지 못할 때
세 번째, 조회 작업을 별로 수행하지 않을 때

위와 같은 세 가지 예시가 있습니다.