Per ardua ad astra.

이중 연결 리스트(Doubly Linked List) 응용 프로그램에서의 특정 노드에서 양방향으로 자유롭게 움직일 수 있는 리스트 구조 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 링크가 양방향이므로 양방향으로 검색이 가능해진다. 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있다. 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용된다. 헤드 노드(Head Node)라는 특별한 노드를 추가하는 경우가 많다. 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드를 의미한다. 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 포인터 헤드 노드가 존재하면 삽입, 삭제 알고리즘이 간편해진다. 이중 연결 리스트에서의 노드는 3개의 필드(왼쪽 링크 필드,..

원형 연결 리스트(Circular Linked List) 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트. 한 노드에서 다른 모든 노드로의 접근이 가능하다는 장점이 있다. 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이해진다. 삭제나 삽입 시에는 항상 선행 노드의 포인터가 필요하다. 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다. 코드 #include #include typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; void error(char *message) ..

단순 연결 리스트(Singly Linked List) 단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있다. 마지막 노드의 링크 필드 값은 NULL이다. 첫 번째 노드를 가리키는 포인터(헤드 포인터) 값만 알고 있으면 연결 리스트 안의 모든 노드에 접근이 가능한다. 하나의 단순 연결 리스트는 첫 번째 노드를 가리키는 하나의 포인터만 있으면 충분하다. 헤드 포인터(Head Pointer) : 첫 번째 노드를 가리키는 포인터 코드 #include #include typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; void error(c..

큐(Queue) 큐(Queue) 선입선출(First In First Out, FIFO)의 특징을 갖는 자료구조 큐는 양쪽이 뚫려 있는 구조이다. 한쪽에서는 삽입만 진행되고, 다른 쪽에서는 추출만 진행된다. 큐에 데이터를 삽입하는 동작을 enQueue(인큐)라고 하며, 데이터를 추출하는 동작을 deQueue(데큐)라고 한다. 큐의 중요한 용어로 front(머리)와 rear(꼬리)가 있다. 머리는 저장된 데이터 중 첫 번째 데이터를 가리킨다. 꼬리는 저장된 데이터 중 마지막 데이터를 가리킨다. 첫 번째 데이터 앞을 front가 가리켜야 한다. 데이터 삽입 : enQueue 데이터 추출 : deQueue 구현 ① 큐의 초기화 SIZE = 5 queue = [None for _ in range(SIZE)] fr..

스택(Stack) 스택(Stack) 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)의 특징을 갖는 자료구조 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다. 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 데이터를 추출하는 동작을 pop(팝)이라고 한다. 스택에서는 top(톱)이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다. 구현 ① 스택의 초기화 SIZE = 5 # 스택의 크기 stack = [None for _ in range(SIZE)] top = -1 ② 데이터 삽입 스택이 꽉 찼는지 확인하는 함수 먼저 스택이 꽉 찼는지 확인한 후 스택에 여유 공간이 있..

이진 탐색(Binary Search) 이진 탐색 원리 정렬된 데이터 집합을 검색하는 경우에는 이진 탐색(Binary Search)을 주로 사용하는데, 순차 탐색에 비해서 엄청난 성능으로 데이터를 검색할 수 있다. 이진 탐색은 전체를 반씩 잘라내서 한쪽을 버리는 방식을 사용한다. 데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다. 찾는 값을 검색하고자 1단계에서 중앙 위치를 기준으로 잡는다. 찾는 값이 왼쪽 구역에 있을 경우, 오른쪽 구역을 버린다. 이 과정을 찾을 값을 찾을 때까지 반복한다. 구현 이진 탐색 구현은 키를 찾기 위해 계속 시작, 중앙, 끝을 반복적으로 1/2씩 줄여 가면서 계산하는 방식이다. 검색할 범위를 1/2씩 반복해서 분할하는 기법을 분할 정복(Divide ..

순차 탐색(Sequential Search) 순차 탐색 어떤 데이터는 정렬되지 않은 상태로 존재하고, 어떤 데이터는 정렬된 상태로 존재한다. 이 두 경우에 데이터를 찾는 방법은 조금 다르다. ① 정렬되지 않은 집합에서의 순차 탐색 검색 성공 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다. 검색 실패 첫 번째 데이터부터 차례로 비교해서 찾지 못할 경우, -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다. def seqSearch(ary, fData) : pos = -1 size = len(ary) print('## 비교한 데이터 ==> ', end = '') for i in range(size) : print(ary[i], end = ' ') if ary[i] == fData..

원형 연결 리스트(Circular Linked List) 원형 연결 리스트의 개념 단순 연결 리스트(Singly Linked List) 끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 한다. 원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정되어 리스트 형태가 원(Circle) 형태로 구성된다. 시작 위치와 다음 위치가 계속 이어진 후, 마지막에 다시 시작 위치로 돌아오는 형태 원형 연결리스트는 단순 연결 리스트와 마찬가지로 데이터 삽입에서 오버헤드가 발생하지 않는다. 원형 연결 리스트의 원리 원형 연결 리스트의 원리 및 구조도 단순 연결 리스트와 많은 부분이 비슷하다...

단순 연결 리스트(Singly Linked List) 단순 연결 리스트의 개념 선형 리스트(Linear List) 장점 배열에 구성하였기 때문에 단순하다. 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다. 프로그램으로 구현하기 비교적 쉽다. 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다. 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생) 단순 연결 리스트(Singly Linked List) 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다. 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다. 데이터와 링크로 구..

선형 리스트(Linear Linked List) 선형 리스트의 기본 개념 데이터를 일정한 순서로 나열한 구조 순차 리스트(Ordered List)라고도 한다. 입력 순서대로 저장하는 데이터에 해당한다. 선형 리스트는 다양한 방법으로 구현할 수 있지만, 가장 기본적인 방법은 배열 을 이용하는 것이다. 선형 리스트는 메모리에서도 차례로 저장된다. 원리 데이터 삽입 1단계 : 맨 끝에 빈칸을 확보한다. 2단계 : 삽입하고자 하는 공간에 빈칸이 없으므로, 삽입하고자 하는 공간 뒤에 있는 요소들을 한칸씩 뒤로 옮긴다. 3단계 : 빈자리에 요소를 삽입한다. 데이터 삭제 원하는 요소가 삭제된 후 빈칸을 그대로 두지 않고 뒤의 요소들을 앞으로 한칸씩 이동시킨다. 선형 리스트의 구현 사용자가 입력하는 데이터가 가변적으로..