- 순차 리스트(ArrayList): 배열 기반으로 구현된 리스트 => 논리적인 순서와 물리적인 순서가 같다.
- 연결 리스트(LinkedList): 메모리의 동적 할당을 기반으로 구현된 리스트
리스트의 특징
- 데이터를 나란히 저장한다.
- 중복된 데이터의 저장도 허용된다.
- 임의의 위치에 있는 항목에 대한 연산이 허용된다.
배열 기반 리스트의 장점
- 데이터의 참조가 쉬움
배열 기반 리스트의 단점
- 배열의 길이가 초기에 결정되어야하고 중간에 변경이 불가능하다.
- 삭제의 과정에서 데이터의 이동이 자주 발생한다.
리스트의 추상 자료형
데이터
임의의 접근 방법을 제공하는 같은 타입의 요소들이 나란히 저장된 자료구조
연산
init(): 리스트의 초기화
insert(): 요소 삽입
delete(): 요소 삭제
get(): 요소 반환
isEmpty(): 리스트가 비어있는지 확인
isFull(): 리스트가 가득찼는지 확인
replace(): 요소 교체
size(): 요소의 개수 반환
find(): 요소가 있는지 확인
clear(): 리스트를 비움
아래는 c에서 배열을 기반으로 리스트의 구현입니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 100
typedef int Element;
Element data[MAX_LIST_SIZE];
int length = 0;
//초기화
void init() {
length = 0;
};
//비우기
void clear() {
length = 0;
};
//비어있는지 확인
int isEmpty() {
return length == 0;
};
//가득 찼는지 확인
int isFull() {
return length == MAX_LIST_SIZE;
};
//pos 위치에 e삽입
void insert(int pos, Element e) {
if(!isFull() && pos <= length) {
for (int i = pos; i < length; i++) {
data[i + 1] = data[i];
}
data[pos] = e;
length++;
}
};
//pos 위치에 있는 데이터 삭제
void delete(int pos) {
if (!isEmpty() && pos <= length) {
for (int i = pos; i < length; i++) {
data[i] = data[i + 1];
}
length--;
}
};
//pos 위치에 있는 데이터를 e로 교체
void replace(int pos, Element e) {
data[pos] = e;
};
//pos 위치에 있는 데이터 반환
int get(int pos) {
return data[pos];
};
//e와 값이 같은 데이터를 찾으면 해당 데이터의 인덱스 반환
int find(Element e) {
if (!isEmpty()) {
for (int i = 0; i < length; i++) {
if (e == data[i]) return i;
}
}
};
//리스트 내부의 요소 전부 출력
void printList() {
if (!isEmpty()) {
for (int i = 0; i < length; i++) {
printf("%d ", data[i]);
}
printf("\n");
}
}
//리스트의 요소의 개수
int size() {
return length;
};
