[Data Structures] 배열과 연결 리스트

📊 배열(Array)

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조다.
주로 데이터의 빠른 접근이 필요한 경우에 사용된다.

📂 배열의 특징

1. 인덱스를 통한 접근

   • 인덱스를 사용해 O(1) 시간에 데이터를 빠르게 접근할 수 있다.
   • 데이터의 위치를 바로 알 수 있어 검색이 효율적이다.

2. 연속된 메모리 공간

   • 데이터가 메모리 공간에 연속적으로 저장된다.
   • 캐시 지역성(Cache Locality) 덕분에 성능이 향상된다.

3. 고정된 크기

   • 선언 시 크기가 고정되며, 크기 변경 시 새로운 배열을 생성해야 한다.

💡 배열의 장단점

• 장점

  • 인덱스를 사용한 빠른 데이터 접근이 가능하다.
  • 구조가 간단하고 사용이 용이하다.
  • 연속된 메모리 공간 덕분에 캐시 성능이 뛰어나다.

• 단점

  • 크기가 고정적이므로 유연성이 떨어진다.
  • 중간 데이터 삽입/삭제 시 데이터 이동이 필요하다.
  • 배열 크기가 고정되어 있어, 크기를 초과할 경우 메모리 낭비나 부족이 발생할 수 있다.

---

🔗 연결 리스트(Linked List)

연결 리스트는 데이터를 저장하는 각 노드가 다음 데이터를 가리키는 포인터로 연결된 자료구조다.

🧬 연결 리스트의 구조

1. 노드(Node)

   • 데이터 필드: 저장할 데이터를 포함한다.
   • 링크 필드: 다음 노드의 주소를 포함한다.

2. 종류

   • 단순 연결 리스트: 각 노드는 다음 노드만 가리킨다.
   • 이중 연결 리스트: 각 노드는 이전과 다음 노드를 모두 가리킨다.
   • 원형 연결 리스트: 마지막 노드가 첫 번째 노드를 가리킨다.

🧵 연결 리스트의 특징

1. 동적 크기

   • 크기가 동적으로 변하며, 메모리를 효율적으로 사용할 수 있다.

2. 데이터 삽입/삭제

   • 중간에 데이터를 삽입하거나 삭제할 때 포인터만 변경하면 된다.
   • 배열과 달리 데이터 이동이 필요 없다.

3. 메모리 사용

   • 연속적이지 않은 메모리 공간을 사용할 수 있다.
   • 각 노드마다 추가 메모리(포인터)가 필요하다.

🪜 연결 리스트의 장단점

• 장점

  • 크기를 동적으로 조절할 수 있다.
  • 삽입과 삭제가 효율적이다.
  • 메모리를 유연하게 사용할 수 있다.

• 단점

  • 특정 위치의 데이터에 접근하려면 순차적으로 탐색해야 한다.
  • 포인터로 인한 추가 메모리가 필요하다.
  • 연속된 메모리 공간에 데이터를 저장하지 않아서, 캐시 지역성이 낮아 성능이 저하될 수 있다.

---

⚖️ 배열 vs 연결 리스트

특징	배열	연결 리스트
메모리 구조	연속된 메모리 공간	노드와 포인터로 연결된 구조
접근 속도	빠름 (O(1))	느림 (O(n))
삽입/삭제 속도	느림 (데이터 이동 필요)	빠름 (포인터 변경만 필요)
메모리 사용 효율성	크기 고정, 낭비 가능	크기 가변적, 효율적 사용
캐시 성능	캐시 친화적	캐시 성능 낮음

---

🧐 결론

• 배열은 데이터 크기가 고정적이고 빠른 접근이 필요할 때 적합하다.
• 연결 리스트는 데이터 크기가 가변적이고 삽입/삭제가 빈번할 때 적합하다.

적절한 자료구조를 선택하는 것은 프로그램의 성능을 좌우할 수 있으므로, 각각의 장단점을 잘 이해하고 상황에 맞게 활용하자.