#2 배열과 리스트

1. 🔲 배열(Array)

배열은 고정된 크기의 연속된 메모리 공간에 데이터를 저장하는 자료구조입니다. 인덱스를 통해 각 데이터에 빠르게 접근할 수 있으며, 크기가 고정되어 있어 메모리 관리가 효율적입니다. 그러나 크기를 동적으로 조절할 수 없고, 데이터의 삽입과 삭제가 불편한 단점이 있습니다.

 

배열의 특징

• 고정 크기: 배열을 선언할 때 크기를 미리 정해야 하며, 크기 변경이 불가능합니다.
• 인덱스 기반 접근: 배열은 인덱스를 이용해 데이터를 바로 접근할 수 있어, O(1) 시간 복잡도로 빠르게 데이터를 찾을 수 있습니다.
• 연속된 메모리 공간: 배열은 메모리 상에 연속적으로 저장되어 캐시 효율성이 좋고, 데이터 접근 속도가 빠릅니다.

 

📊 배열의 시간 복잡도

• 데이터 접근: O(1)
• 삽입/삭제 (중간에 삽입/삭제): O(n) (배열 크기를 변경하거나, 요소를 이동시켜야 하기 때문에)

 

---

 

2. 🔗 연결 리스트(Linked List)

연결 리스트는 데이터를 노드 단위로 연결한 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있어, 데이터를 삽입하거나 삭제할 때 빠르게 작업할 수 있습니다. 하지만 특정 요소에 접근하려면 순차적으로 탐색해야 하므로, 배열보다 검색 속도가 느릴 수 있습니다.

 

연결 리스트의 특징

• 동적 크기: 연결 리스트는 데이터의 삽입과 삭제가 유연하게 이루어지며, 크기를 동적으로 변경할 수 있습니다.
• 포인터 기반 접근: 연결 리스트는 데이터를 배열처럼 인덱스로 바로 접근할 수 없고, 포인터를 통해 순차적으로 탐색해야 하므로 **O(n)**의 시간 복잡도를 가집니다.
• 연속되지 않은 메모리 공간: 연결 리스트의 노드는 메모리 상에서 연속적으로 저장되지 않으므로, 캐시 효율성이 떨어질 수 있습니다.

 

📊 연결 리스트의 시간 복잡도

• 삽입/삭제 (맨 앞/중간/맨 뒤 삽입): O(1) (단, 특정 위치를 찾는 데는 O(n))
• 데이터 접근: O(n)

 

연결 리스트의 종류

• 단일 연결 리스트(Singly Linked List): 각 노드는 다음 노드만을 가리킵니다.
• 이중 연결 리스트(Doubly Linked List): 각 노드는 이전 노드와 다음 노드를 모두 가리킵니다.
• 순환 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 구조입니다.

 

---

 

3. 🔲 ArrayList

ArrayList는 **동적 배열(Dynamic Array)**을 기반으로 한 자료구조입니다. 기본적으로 배열의 특성을 가지면서, 배열의 크기를 동적으로 조정할 수 있어 유연성을 제공합니다. 데이터 삽입 및 삭제 시 자동으로 크기가 조정되지만, 배열처럼 인덱스를 통한 빠른 접근이 가능합니다. 다만, 데이터 삽입/삭제가 자주 발생하는 경우 배열을 재할당하고 요소를 이동시켜야 하기 때문에 성능이 다소 떨어질 수 있습니다.

 

ArrayList의 특징

• 동적 크기: 초기 크기를 정할 필요가 없으며, 데이터가 추가되면 내부적으로 배열의 크기가 자동으로 확장됩니다. 크기가 부족하면 새 배열을 할당하고 기존 데이터를 복사하여 확장합니다.
• 인덱스 기반 접근: 배열처럼 인덱스를 사용하여 데이터를 빠르게 조회할 수 있습니다. 이로 인해 **O(1)**의 시간 복잡도로 데이터 접근이 가능합니다.
• 연속된 메모리 공간: 배열을 사용하여 데이터를 저장하므로, 배열처럼 메모리 상에서 연속적으로 저장됩니다. 캐시 효율성이 좋고, 데이터 접근 속도가 빠릅니다.
• 비효율적인 삽입/삭제: 배열의 크기를 동적으로 조정할 때, 요소를 이동하거나 배열을 재할당해야 하므로 삽입과 삭제는 O(n) 시간이 걸릴 수 있습니다.

 

📊 ArrayList의 시간 복잡도

• 데이터 접근: O(1)
  배열처럼 인덱스를 사용하여 데이터를 빠르게 찾을 수 있습니다.
• 삽입/삭제 (맨 끝에 삽입/삭제): O(1)
  배열의 끝에 데이터를 추가하거나 삭제하는 것은 빠릅니다.
• 삽입/삭제 (중간에 삽입/삭제): O(n)
  배열 중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 데이터를 이동시켜야 하므로 시간이 많이 소요됩니다.
• 크기 조정: O(n)
  배열의 크기가 부족할 때, 새로운 배열을 할당하고 기존 데이터를 복사하는 데 시간이 걸립니다.

 

---

 

• 4. 배열 vs 리스트 (Array vs Linked List vs ArrayList)

 

🆚 배열(Array) vs 연결 리스트(Linked List)

• 배열(Array):
  • 빠른 검색: 배열은 인덱스를 이용해 빠르게 데이터를 검색할 수 있습니다. 접근이 O(1) 시간 복잡도로 빠릅니다.
  • 고정 크기: 배열은 크기가 고정되어 있고, 크기를 변경할 수 없으며, 삽입과 삭제가 어렵습니다.
  • 데이터 접근의 효율성: 배열은 연속된 메모리 공간에 저장되기 때문에 캐시 효율성이 높고 빠른 데이터 접근이 가능합니다.
• 연결 리스트(Linked List):
  • 빠른 삽입/삭제: 연결 리스트는 포인터를 사용하기 때문에, 데이터 삽입과 삭제가 매우 빠릅니다. 특히 중간에 데이터를 삽입/삭제할 때 **O(1)**의 시간 복잡도를 가집니다.
  • 검색 속도: 배열처럼 인덱스를 사용할 수 없기 때문에 데이터를 찾는 데 O(n) 시간이 걸립니다.
  • 동적 크기: 연결 리스트는 크기가 동적으로 변하며, 크기를 미리 지정할 필요가 없습니다.

적합한 상황:

• 배열: 데이터를 자주 조회하고 인덱스를 활용한 빠른 접근이 필요한 경우.
• 연결 리스트: 데이터의 삽입/삭제가 빈번하게 발생하고, 크기가 동적으로 변해야 할 때.

---

🆚 Array vs ArrayList vs LinkedList

• Array:
  • 고정 크기 배열.
  • 빠른 데이터 접근: 인덱스를 통해 빠르게 값을 검색할 수 있습니다.
  • 크기 변경 불가: 배열의 크기는 선언 시 고정되며, 이후 크기 변경이 불가능합니다.
• ArrayList:
  • 동적 크기 배열입니다. 크기를 미리 정의할 필요가 없고, 데이터 삽입/삭제 시 배열의 크기를 자동으로 조정합니다.
  • 빠른 데이터 접근: 배열처럼 인덱스를 통해 빠르게 데이터를 검색할 수 있습니다.
  • 단점: 데이터 삽입/삭제 시 배열을 재할당하고 요소들을 이동해야 하므로 속도가 상대적으로 느립니다.
• LinkedList:
  • 포인터 기반 연결 자료구조입니다. 데이터를 삽입하거나 삭제하는 데 매우 유리합니다.
  • 삽입/삭제 효율성: 삽입과 삭제는 O(1) 시간 복잡도로 매우 빠릅니다.
  • 검색 비효율성: 특정 노드를 찾는 데 O(n) 시간이 걸립니다.

---

🆚 Array vs ArrayList 차이점

• 배열(Array):
  • 사이즈: 초기화 시 고정된 크기를 가집니다.
  • 크기 변경: 크기 변경이 불가능합니다.
  • 속도: 메모리에 할당된 크기만큼 데이터를 저장하며, ArrayList보다 속도가 빠릅니다.
• ArrayList:
  • 사이즈: 초기화 시 크기를 지정하지 않으며, 크기가 동적으로 변경됩니다.
  • 크기 변경: 데이터 삽입과 삭제 시 크기가 동적으로 증가하거나 감소합니다.
  • 속도: 데이터 추가/삭제 시 메모리를 재할당하고 요소들을 이동시켜야 하므로 속도가 Array보다 느립니다.

---

🆚 ArrayList vs LinkedList

• ArrayList:
  • 기본적으로 배열을 사용하여 인덱스를 통한 빠른 데이터 접근이 가능합니다.
  • 데이터 삽입/삭제 시, 위치를 맞추는 작업이 필요하여 비효율적입니다. 데이터의 추가/삭제가 많다면 비효율적입니다.
• LinkedList:
  • 데이터를 삽입하거나 삭제하는 데 유리한 자료구조입니다. 데이터와 포인터를 사용하여 삽입/삭제가 빠릅니다.
  • 특정 요소를 찾는 데는 O(n) 시간이 걸려 비효율적입니다. 연결 리스트는 순차적 탐색만 가능하므로 검색에 불편함이 있습니다.

---

정리)

• **배열(Array)**는 인덱스를 통한 빠른 접근이 필요하고, 크기가 고정된 데이터에 유리합니다.
• ArrayList는 크기가 가변적이어서 데이터를 동적으로 다룰 수 있으며, 검색은 빠르지만 삽입/삭제에서 비효율적입니다.
• LinkedList는 데이터의 삽입/삭제가 많을 때 유리하며, 검색에서 성능이 떨어집니다.

 

✅ 데이터 추가/삭제가 많은 경우에는 LinkedList

✅ 검색이 많고 크기를 동적으로 변경할 필요가 없는 경우에는 Array나 ArrayList