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

---

1. 자료구조의 분류

• 단순구조:
  • 단순히 데이터를 저장하고 관리.
• 비단순구조:
  • 데이터 간의 관계를 표현하며, 선형구조와 비선형구조로 나뉨.
  • 선형구조: 데이터가 순차적으로 나열되는 구조
    • 예시 : 배열, 연결리스트. 스택, 큐, 덱(DQueue), 
  • 비선형 구조: 데이터가 순차적으로 나열되지 않는 구조
    • 예시 : 트리, 그래프, 집합, 해시맵, 해시테이블, 

---

 

2. 배열 (Array)

2.1 배열의 정의와 특징

• 정의:
  • 동일한 데이터 타입의 데이터를 연속적인 메모리에 저장.
  • 물리적 순서와 논리적 순서가 동일.

배열의 구조

• 2.2 배열의 장점
  • 빠른 접근:
    • 데이터의 위치를 알고 있다면, 인덱스를 통해 즉시 접근 가능 (시간복잡도: O(1))

배열의 접근

2.3 배열의 단점

• 삽입과 삭제 속도 저하:
  • 데이터 삽입/삭제 시, 배열을 재생성하고 데이터를 복사해야 함.
  • 시간 소요가 크며, 메모리 소모도 많음 (시간복잡도: O(n)).

배열의 삽입 과정

---

3. 연결리스트 (Linked List)

3.1 연결리스트의 정의와 특징

• 정의:
  • 노드(Node)를 기본 단위로, 데이터를 저장하고 다음 노드의 참조값(Pointer)을 연결하는 구조.
• 특징:
  • 고정된 크기가 없으며, 연속된 메모리를 사용하지 않음.
  • 데이터 삽입/삭제 시, 노드의 참조값만 변경.

연결리스트 구조

3.2 연결리스트의 장점

• 삽입과 삭제가 빠름:데이터 이동 없이, 참조값만 변경 (시간복잡도: O(1)).

 

3.3 연결리스트의 단점

• 메모리 소모:
  • 데이터와 참조값을 저장하기 위한 추가 메모리 필요.
• 데이터 접근 속도 저하:
  • 참조값을 따라가야 하므로, 데이터 접근 시간이 길어짐 (시간복잡도: O(n)).     

---

4. 연결리스트의 종류

• 단일 연결 리스트:
  • 각 노드가 다음 노드만 참조.
• 이중 연결 리스트:
  • 각 노드가 이전 노드와 다음 노드를 참조.
• 원형 연결 리스트:
  • 마지막 노드가 첫 번째 노드를 참조하여 원형 구조를 형성.

연결리스트 이미지화

---

5. 배열과 연결리스트 비교

종류	배열	연결리스트
크기	고정	동적
메모리 주소	연속	불연속
데이터 접근 시간	O(1)	O(n)
삽입/삭제 시간	O(n)	O(1)

---

6. 포인트

• 데이터 접근 시간에 대한 시간복잡도에 대해서 작성된 값은 탐색이 아닌 접근의 관점에서 계산한 부분
• 즉, 해당 데이터가 어디 있는지를 알고 접근한다고 가정한 결과
• 배열은 복도가 있는 호텔 방들이라 생각하면 됨. [401호라고 하면, 바로 401호로 들어가면 됨]
• 연결리스트는 기차 칸이라 생각하면 쉬움 [1호차에서 5호차로 가기위해선, 2/3/4호차를 거쳐서 가야함]
• 배열의 접근 시간 복잡도 : O(1):
• 연결리스트의 시간 복잡도 : O(n)

---

7. 결론

• 배열: 데이터 접근이 빠르며, 크기가 고정된 데이터를 다룰 때 적합.
• 연결리스트: 삽입/삭제 연산이 잦고, 데이터 크기를 사전에 알 수 없는 경우 적합.
• 선택 기준
  • 데이터의 특성과 사용 목적에 따라 적합한 자료구조를 선택해야 함.
  • 예: 배열은 접근 중심, 연결리스트는 삽입/삭제 중심의 작업에 유리.

---