지난 시간 복기
반복적 방법은 구현이 쉽고, 대다수는 걸리는 시간도 순환적 방법보다 빠르다.
그리고 순환적 방법은 함수를 계속 호출을 함으로써 메모리도 많이 잡아먹고(메모리의 스택공간), 결국 스택공간이 가득차서 더이상 연산할 수 없는 상황이 발생하기도 한다(오버플로우)
그렇지만,
어려운 알고리즘을 구현하는 상황이나, 거듭제곱을 구하는 경우(정말 예외적 경우에 가까움)에는 순환적 방법이 오히려 걸리는 시간도 짧고, 구현하기가 더 편하다.
피보나치 수열 계산
순환 호출의 경우의 비효율성
•
같은 항이 중복해서 계산됨
•
fib(6)을 호출하는 경우에, fib(3)이 4번이나 중복되어 계산됨
◦
스택에도 중복적으로 쌓이고 해서 좋지 않다!
이제 본격적으로 자료구조 내용 시작!
리스트(Lists)
List
•
선형 리스트
◦
배열
•
연결 리스트
Stack
•
선형 리스트
◦
배열
•
연결 리스트
•
동적 배열
Queue
•
선형 리스트
◦
배열
•
연결 리스트
•
동적 배열
학습 목표
•
리스트의 개념
•
리스트를 배열 이용해서 구현
•
리스트를 연결 리스트를 이용해서 구현
내용
•
List ADT
•
Sequential List(배열로 구현된 리스트)
•
Linked List(연결리스트)
•
Singly Linked List(단순 연결 리스트)
List vs Set
List
순서O, 중복O ← Index
Set
집합
순서X, 중복X
Array List VS Linked List
무조건 좋거나, 무조건 나쁜 리스트는 없다
모두 장단점이 존재한다
Array List
•
순서가 있고, 연속성이 있다
◦
insert한다면, 무조건 인덱스값이 작은 순서대로 넣어줘야한다.
◦
연속성을 유지해야하므로, 중간에 비어있으면 안되고
만약 중간값이 배열에서 삭제된다면, 데이터를 앞으로 당겨줘야한다.
즉, 데이터의 삽입과 삭제가 비효율적이다
▪
그러나, 빠르기는 ArrayList가 빠르다. 연결리스트는 overhand가 필요해서 찾는데 시간이 좀 걸리기 때문이다.
Linked List
•
물리적으로는,
순서가 존재하지 않아도 된다
그러나
•
논리적으로는,
순서가 존재해야한다.
◦
연결되어있는 다음 데이터값의 주소를 알아야한다(Overhand 필요)
데이터의 삽입과 삭제가 편리하고 효율적이다
데이터가 추가로 들어오거나 나가는 경우에, 그냥 연결만 해주면 됨
ArrayListType 구현
#define MAX_LIST_SIZE 100
typedef int element;
typedef struct {
element array[MAX_LIST_SIZE];
int size;
} ArrayListType;
C
복사