연결리스트 덱 - 연결리스트를 이용한 덱 (이중 연결 리스트) - front, rear 둘다 삽입/삭제가 되기 때문에 이중 연결 리스트로 구현 [코드 - C] #include #include // 연결리스트를 이용한 덱 (이중 연결 리스트) // front, rear 둘다 삽입/삭제가 되기 때문에 이중 연결 리스트로 구현 typedef int element; typedef struct dnode{ element data; struct dnode* llink; struct dnode* rlink; }dnode; dnode* front; dnode* rear; int is_empty() { return front == NULL; // 공백 상태이면 front == NULL } void add_rear(ele..

연결리스트 큐 - front : 삭제(delete) - rear : 삽입(insert) - rear의 link 필드는 NULL로 설정해야 한다 - 초기 상태 : front == rear == NULL - 공백 상태 : front == NULL [코드 - C] #include #include // 연결리스트를 이용한 큐 typedef int element; typedef struct qnode { element data; struct qnode* link; }qnode; qnode* front = NULL; // 큐의 front(삭제와 관련) qnode* rear = NULL; // 큐의 rear(삽입과 관련) int is_empty() { return front == NULL; // 공백 상태이면 fro..

연결리스트 스택 - 장점 : 크기 제한 X - 단점 : 구현이 복잡, 삽입/삭제 시간이 오래 걸린다 - 크기에 제한이 없기 때문에 스택이 포화인지 확인할 필요가 없다 [코드 - C] #include #include // 연결리스트를 이용한 스택 typedef int element; typedef struct { element data; struct stacknode* link; // 각 노드들을 연결 }stacknode; stacknode* top; // 스택의 top을 가리키는 top 포인터 void init() { top = NULL; } int is_empty() { return top == NULL; } void push(element item) { stacknode* new_node = (sta..

이중 연결 리스트 (Doubly Linked List) - 링크가 양방향 이기 때문에 양방향 검색이 가능 - 삽입/삭제시 반드시 선행 노드가 필요 - 공간을 많이 차지하고 코드가 복잡하다 - 헤드 노드를 보유 - 헤드 노드 + 이중 연결 리스트 + 원형 연결 리스트로 구현할 예정 ※ 헤드 노드 / 헤드 포인터 헤드 노드 - 데이터 필드에 아무런 정보도 담고 있지 않다 → 데이터를 가지지 않는다 - 단지, 삽입/삭제의 편리함을 위해 구현 - 공백상태에서는 헤드 노드만 존재 헤드 포인터 - 리스트의 첫 번째 노드를 가리키는 포인터 ※ 항상 성립하는 관계 - 임의의 노드를 가리키는 포인터 p p = p->llink->rlink = p->rlink->llink 이중 연결 리스트의 노드 구조 - 1개의 데이터 필..

원형 연결 리스트 (Circular Linked List) - 마지막 노드의 링크가 첫 번째 노드의 주소를 가리키는 리스트 - 하나의 노드에서 모든 노드에 접근 가능 - 헤드 포인터가 항상 마지막 노드를 가리키게 설정 1. 삽입 연산 ① 리스트의 맨 앞에 삽입 head == NULL인 경우 : new_node를 insert하게 되면 헤드 포인터가 new_node를 가리키게 된다 void insert_first(c_listnode** head, c_listnode* new_node) { // 리스트 맨 처음에 new_node 삽입 if (*head == NULL) { // head가 NULL => 공백리스트 상태 // new_node를 insert하게되면 head pointer는 new_node를 가리키게..

단순 연결 리스트 (Singly Linked List) - 단방향 연결 - 마지막 노드의 링크값 = NULL - 헤드 포인터 : 연결 리스트의 맨 처음 노드를 가리키는 포인터 단순 연결 리스트 ADT void insert_node(s_listnode **head, s_listnode *pre, s_listnode *new_node) 삽입연산 void remove_node(s_listnode **head, s_listnode *pre, s_listnode *removed) 삭제연산 void print_list(s_listnode *head) 리스트 순서대로 출력 s_listnode *search(s_listnode *head, int value) 리스트안에 존재하는 value 찾아내기 s_listnode ..

연결 리스트 (Linked-List) - 각 상자들을 연결하는 줄 : 포인터로 구현 - 각 상자들 : 노드 - 필요할 때마다 동적 메모리 할당(malloc())을 통해 노드 생성 - 노드 : 데이터 필드/링크 필드로 구성 - 데이터 필드 : data(값) 존재 - 링크 필드 : 다른 노드를 가리키는 포인터 존재 → 포인터를 이용하여 다음 노드에 접근 - 첫 번째 노드를 알면 전체 노드에 접근 가능 - 첫 번째 노드를 가리키는 변수 : 헤드 포인터 (head pointer) - 마지막 노드의 링크 필드 = NULL (더 이상 연결된 노드 X) - 실제 메모리 안의 물리적 순서 ≠ 리스트 안의 논리적 순서 연결 리스트의 장단점 (삽입/삭제) 장점 - 삽입/삭제 시 데이터를 이동할 필요가 없다 - 연속된 메모..

리스트 - 순서를 가진 데이터들의 모임 - ex) 오늘 해야 할 일 : (청소, 쇼핑, 영화 관람), 요일들 : (일, 월, 화,... 토) 리스트 ADT - n개의 element형으로 구성된 순서가 있는 모임 void init_list(ArrayList *L) 리스트 초기화 int is_empty(ArrayList *L) 공백 상태 검출 함수 int is_full(ArrayList *L) 포화 상태 검출 함수 void insert(ArrayList *L, int pos, element item) 리스트의 pos위치에 item 삽입 void insert_last(ArrayList *L, element item) 리스트의 last에 item 삽입 void insert_first(ArrayList *L, e..

덱 (Deque - Double Ended Queue) - 큐(Queue) : 전단(front)에서 삭제, 후단(rear)에서 삽입 - 덱(Deque) : 큐의 전단(front), 후단(rear)에서 모두 삽입/삭제 가능 ※ Example - delete_rear / add_front - MAX_DEQUE_SIZE = 5 front rear 과정 0 0 Deque 초기화 0 1 add_rear 0 2 add_rear (1) 4 2 add_front (2) 3 2 add_front → 포화 4 2 delete_front 0 2 delete_front (3) 0 1 delete_rear (4) 0 0 delete_rear → 공백 (1) → (2) front에서 add를 하려면 원래 front 인덱스에 it..

선형큐 문제점 가득 차지 않았지만, rear가 마지막 인덱스를 가리키고 있을 경우 -> euqueue하기 위한 공간을 마련해야 하기 때문에 전체 데이터를 이동 -> 비효율적인 작업 발생 -> 해결 : 원형큐 원형큐 (Circular Queue) - 배열의 끝 (MAX_QUEUE_SIZE -1)에 도달하면 다음 증가되는 값 = 0 - 초기화 상태 : front = rear = 0 - front : 항상 큐의 첫 번째 요소에서 하나 전 - rear : 마지막 item의 인덱스 공백 상태/포화 상태를 구분하기 위해 항상 1칸은 비워둔다 공백 상태 : front == rear 포화 상태 : front가 rear보다 하나 다음 ※ Example (enqueue / dequeue 반복을 통한 인덱스 변화) - MA..

큐 (Queue) - FIFO(First in - First out) 선입 선출 구조 - 전단(front) : 삭제가 일어나는 곳 - 후단(rear) : 삽입이 일어나는 곳 큐 ADT (추상 자료형) - 0개 이상의 요소들로 구성된 선형 리스트 void init_queue(queue *q) 큐 초기화 int is_full(queue *q) 포화 상태 검출 함수 int is_empty(queue *q) 공백 상태 검출 함수 void enqueue(queue *q, element item) 큐의 후단(rear)에 item 삽입 element dequeue(queue *q) 큐의 전단(front)에서 item 리턴 후 삭제 element peek(queue *q) 큐의 전단(front)에서 item 선택 선형..

알고리즘 현재 위치에서 갈 수 있는 모든 위치(상하좌우) 모두 stack에 push --(1) stack에서 pop 시켜서 pop 시킨 것을 현재 위치로 설정하고 (1) 계속 반복 -> 갈 곳 = stack에서 pop, 안 간 곳 = 그대로 stack에 존재 -> 이미 간 곳을 또 가면 이미 stack에 1번 저장되었기 때문에 다시 stack에 push X typedef struct { int r; // 로우(row) int c; // 컬럼(column) }cur_locate; // 현재 위치를 좌표 (r, c)로 표현 typedef struct { int top; cur_locate maze[MAX_STACK_SIZE]; }stack; char maze[MAZE_SIZE][MAZE_SIZE] = { /..