리스트(List)#1

리스트(List, Linear List)

데이터를 순서대로 나열한 형태의 자료구조이다.

 

 - 순차 리스트(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;
};