[자료구조] 기초데이터구조 | 배열, 연결리스트

---

✅ 3.1 데이터구조의 기본 재료

건물에 비유하면

데이터구조: 건물을 구성하는 재료, 자재, 이들이 상호 결합된 구조물

알고리즘: 건물을 조명하고, 냉난방을 공급하거나, 환기시키며, 비상시 작동하는 자동 개폐 시스템 등 건물을 운영하는 일련의 제어 시스템

---

잘 설계된 조명 배치나 냉난방 배관 구조가 (데이터구조)

건물의 조명과 냉난방의 운용 효율과 경제성 면에서 긍정적인 영향을 미치는 것처럼 (알고리즘)

좋은 데이터구조 설계는 효율적인 알고리즘 운용의 선결 조건이다!

---

데이터구조를 구축하는 기본 재료로서 배열과 연결리스트 공부하기

배열과 연결리스트는 차후 한 차원 높은 형태의 데이터구조 설계에 기본 재료 역할을 한다 :)

 

차후에 학습할 데이터구조들은 이 장에서 습득할 배열이나 연결리스트에 의해 상세 구현됨

이어지는 장에서 다룰 데이터구조들이 비교적 추상적이고 인간의 사고에 더 가깝다고 한다면,

배열과 연결리스트는 구체적이고 컴퓨터구조에 더 가까움

---

✅ 3.2 배열

🔅 3.2.1 1차원 배열

배열(array): 순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터원소

 

🔅 3.2.2 다차원 배열

➰ 2차원 배열

➰ 3차원 배열

 

➰ 4차원 배열

 

---

✅ 3.3 연결리스트

연결리스트(linked list): 동적메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터원소 노드들

연결리스트를 이해하기 위해 우선 동적메모리와 노드의 개념을 알아야 함.

동적메모리(dynamic memory): 프로그램 실행 시에 프로그램에 의해 사용가능한 주메모리의 한 구역

노드(node): 한 개의 데이터원소를 저장하기 위해 동적메모리에 할당된 메모리

노드를 위한 메모리의 할당(allocation)과 해제(deallocation)는 실행시간의 시스템 콜에 의해 처리됨

- getnode(): 노드를 할당하고, 그 노드의 주소를 반환. 만약 동적메모리가 고갈된 시점이면 널(null) 반환

- putnode(): 주소 i의 노드에 할당되었던 메모리의 사용을 해제하고, 이를 동적메모리에 반환(메모리 재활용을 위함)

컴파일 시에 메모리가 할당되는 배열과 달리,

연결리스트의 노드들을 위한 메모리는 동적할당, 즉 프로그램 실행 시 할당됨에 유의하기

---

🔅 3.3.1 단일연결리스트

단일연결리스트(singly linked list): 연속 노드로 구성된 가장 단순한 연결 데이터구조

- 원소(element): 데이터원소

- 링크(link): 다음 노드의 주소. 다음 노드가 없으면 널링크 저장

 

단일연결리스트의 접근점, 즉 연결리스트 전체에 대한 참조는 첫 노드의 주소를 사용함
이를 헤드노드(head node)라고 함

위 사진의 단일연결리스트에 대한 접근점: 헤드노드의 주소 L

아래부분은 단일연결리스트 L이 초기화되거나 비어있는 상태를 보인다. 즉, 비어있는 연결리스트의 헤드노드 주소는 널이다.

🔅 3.3.2 이중연결리스트

이중연결리스트(doubly linked list): 각 노드에 링크를 하나 더 추가하여
역방향 순회도 가능하도록 구현한 연결리스트

- 원소(element): 데이터원소

- 링크(link): 다음 노드의 주소. 다음 주소가 없으면 널링크 저장.

- 링크(link): 이전 노드의 주소. 이전 주소가 없으면 널링크 저장.

이중연결리스트의 접근점, 헤드노드(head node)의 주소 or 테일노드(tail node)의 주소를 사용
이들은 데이터를 가지지 않는 특별노드

위 사진에서 이중연결리스트에 대한 접근점은 헤드노드의 주소 Head or 테일노드의 주소 Tail이다.

아래부분에 보인 것처럼 이중연결리스트가 초기화되거나 비어 있으면 Head와 Tail값은 모두 널이다.

 

🔅 3.3.3 원형연결리스트

🔅 3.3.4 헤더와 트레일러

🔅 3.3.5 그외의 연결리스트

 

(추후 추가예정)

---

본 게시물은 세종대학교 자료구조 수업교재 '알고리즘 원리와 응용'(국형준 지음)을 정리하였습니다.