배열

일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조

각 요소에는 0부터 시작하는 고유한 순서 번호인 인덱스가 매겨짐
이 인덱스로 배열의 요소를 식별할 수 있음

배열 빅 오 표기법

📌 인덱스 접근

O(1)

• 인덱스를 통해 요소에 접근하는 시간은 요소의 개수와 무관하게 일정함
  - 인덱스를 바탕으로 배열의 특정 요소에 접근하는 시간은 O(1)로 일정
  - 인덱스를 바탕으로 배열의 특정 요소를 수정하는 시간도 O(1)로 일정

📌 순차 접근

O(n)

• 0번 인덱스부터 N번 인덱스까지 원하는 데이터를 찾을때까지 하나씩 인덱스를 탐색해 나감
  - 요소가 N개라면 연산의 상한을 N으로 표현
  

📌 특정 요소 추가/삭제 경우

삽입 혹은 연산 후에 모든 요소들의 재정렬이 이루어진다고 가정하면 시간복잡도는 대략 O(n)
중간에 추가 혹은 삭제된 요소로 인해 이후의 요소들이 이동되어야 하기 때문

📌 다차원 배열

배열 확장

• 배열은 기본적으로 일차원 구조를 가지지만, 이차원, 삼차원 배열로 확장 가능
• 이차원 배열: 배열 속에 배열이 포함된 형태 → 두 개의 인덱스로 요소를 식별
• 삼차원 배열: 배열 속에 배열 속에 배열이 포함된 형태 → 세 개의 인덱스로 요소를 식별

배열 활용성

• 가장 기본적인 자료구조로, 활용도가 높음
• 데이터를 일렬로 나열하여 관리하는 데 유용함
• 다른 자료구조 및 알고리즘 구현의 기반이 됨

배열의 메모리 저장 구조
이차원 배열: 행과 열(row, column) 구조로 저장
삼차원 배열: 행, 열, 깊이(depth) 구조로 저장

📌 정적 배열 / 동적 배열

정적 배열: 프로그램을 실행하기 전에 크기가 고정되어 있는 배열

• 정적 배열의 크기는 원칙적으로 프로그램 실행 도중에 바꾸지 못함

동적 배열: 실행 과정에서 크기가 변할 수 있는 배열

• 포함된 요소의 개수가 동적으로 변할 수 있는 특성 덕분에 프로그램을 실행하기 전에 배열의 크기를 알기 어려운 경우, 유연하게 요소의 개수를 조정해야 하는 경우에 사용할 수 있음

---

연결리스트

노드(Node)의 모음으로 구성된 자료구조

• 저장할 데이터 + 다음 노드의 위치(메모리 주소) 정보를 포함
• 특정 노드에 접근하면 다음 노드의 위치를 알 수 있어 순차적으로 데이터를 탐색 가능
• 첫 번째 노드 → 헤드(Head)
• 마지막 노드 → 꼬리(Tail)

연결 리스트 특징

• 메모리에 연속적으로 저장될 필요 없음 → 불연속적으로 데이터 저장 가능
• 배열과의 차이점
  - 배열: O(1)로 임의 접근 가능(인덱스가 주어진다면)
  - 연결 리스트: O(n)으로 앞에서부터 순차 접근

연결 리스트 장점

• 삽입/삭제 연산에서 유리함
  - 배열처럼 데이터 재정렬이 필요 없음
  - 노드의 위치만 변경하면 되므로 O(1) 만에 삽입/삭제 가능

연결 리스트 종류

📌 싱글 연결 리스트 (Singly Linked List)

• 노드 내에 다음 노드의 위치만 저장
• 한쪽 방향(앞 → 뒤)으로만 탐색 가능
• 이전 노드의 위치를 알기 어려움 → 탐색이 단방향으로만 가능

📌 이중 연결 리스트 (Doubly Linked List)

• 다음 노드의 위치 + 이전 노드의 위치도 저장
• 양방향 탐색 가능 → 탐색 성능 향상
• 단점: 추가적인 저장 공간(메모리 주소 2개)이 필요함

📌 환형 연결 리스트 (Circular Linked List)

• 마지막 노드(꼬리)가 첫 번째 노드(헤드)를 가리키는 형태
• 모든 노드를 여러 번 순회해야 할 때 유용
• 이중 연결 리스트로도 구현 가능 → 헤드의 이전 노드가 꼬리를, 꼬리의 다음 노드가 헤드를 가리키도록 구성

---

참고: 북스터디 - 이것이 취업을 위한 컴퓨터 과학이다 (Chapter 4-2)