[Reading] 열혈강의 자료구조 - CHAPTER 03 - 01

열혈강의 자료구조

자료구조를 본격적으로 배우는 본론의 시작 ‘리스트’

CHAPTER 03 - 리스트

구조가 단순해 가장 널리 사용되는 기초적인 자료구조 중 하나로 스택(Stack), 큐(Queue), 트리(Tree)와 그래프(Graph)등 다른 여러 자료구조의 구현에도 응용되어 사용된다.
자료를 순서대로 저장하는 자료구조를 말하며 여러 개의 자료가 일직선으로 서로 연결된(Sequential) ‘선형 구조’를 의미한다.

배열 리스트: C언어에서 제공하는 배열을 이용해 구현된 리스트, 자료가 일직선으로 “연결”
배열: 같은 자료형의 데이터가 메모리 상 연속적으로 저장

1. 리스트의 개념

문자 리스트 / 문자열 리스트
행렬 (Matrix)
다항식 (Polynomial Equation)

2. 리스트 추상 자료형

리스트 사용에 필요한 기본적인 연산을 정리한 리스트의 추상 자료형으로 리스트를 실제 사용하려면 기본적으로 다음 표에 있는 기능들이 필요하다. (N/A는 해당 값이 존재하지 않거나 필요하지 않다는 의미)

스크린샷 2024-01-14 오후 6 18 32

리스트를 사용하기 위해 리스트 생성 및 생성된 리스트를 삭제할 수 있어야 한다.
연산에서 입력 파라미터 n은 리스트에 저장 가능한 최대 원소 개수 의미
리스트에 원소 추가 및 삭제 기능(추가 시 생성 위치 p 지정)

3. 배열 리스트

배열은 메모리상에 순차적으로 저장된다. 즉, 배열을 구성하는 원소들이 순서대로 연속해 메모리에 저장된다. 따라서 배열 리스트에서의 논리적 순서와 물리적 순서가 같다는 특성이 있다.

배열 리스트의 원소 추가

배열 리스트 중간에 새로운 원소를 추가하려면 새로운 원소가 중간에 삽입될 수 있도록 기존 원소들을 이동시켜 주어야 한다.

배열 리스트의 원소 삭제

중간에 있던 원소를 제거하려면 중간에 발생하는 공백을 메우기 위해 원소의 이동이 필요하다.

“배열 리스트의 경우 중간에 원소가 추가, 제거 됨에 따라 관계없는 원소들의 이동이 필요하다는 단점이 존재한다.”
ex) 10만개의 배열 리스트에서 0번째 인덱스에 원소의 추가가 필요하다면 100000 - 1 번의 이동이 필요..

4. 연결 리스트의 개념

연결 리스트는 리스트를 포인터를 이용해 구현한다는 점에서 배열 리스트와 차이가 있다. 즉, 일련의 자료를 저장함에 있어서 C의 포인터를 이용해 물리적으로 떨어져 있는 자료를 순서대로 연결시켜 놓았다. (배열 리스트 - 물리적 위치, 연결 리스트 - 논리적 위치 –> 배열 리스트(물리적 위치)는 최대 원소 개수를 지정해줘야 함)

스크린샷 2024-01-20 오후 8 15 23

연결 리스트는 자료와 링크로 구성된 노드들로 구성된다. 앞서 배열 리스트에서도 이러한 노드가 사용되었지만, 자료만 저장한다는 점에서 ‘원소 === 노드’ 인 반면, 연결 리스트에서의 노드는 ‘자료 + 링크’를 의미하기에 원소를 포함하는 개념이다(연결 리스트 모든 연산의 기본 단위).

연결 리스트의 노드 추가, 제거는 링크 정보를 추가, 제거 한다는 의미와 동일하다. 배열 리스트의 노드 추가, 제거는 원소의 이동을 의미한다.

스크린샷 2024-01-20 오후 8 18 36