반응형
위의 그림은 자료구조의 범주이다.
메인 글을 보고 싶다면 아래 링크를 참고하길 바란다
[자료구조] - [자료구조 기초] 자료구조의 개념, 추상 자료형, 알고리즘 성능 분석
[자료구조 기초] 자료구조의 개념, 추상자료형, 알고리즘 성능 분석
데브옵스 엔지니어로 일을 하고 있지만 그래도 계속적으로 알고리즘이나 자료구조에 대한 부분은 항상 부족했다. 그래서 운영체제, 자료구조 등 정말 fundamental 한 공부부터 다시 시작해 보려고
buildgoodhabit.tistory.com
리스트
의미적으로 관련이 있는 데이터의 집합, 목록 배열이나 연결리스트를 사용해서 구현
선형 리스트 Linear List
데이터가 연속되는 메모리에 저장 / 배열이나 문자열을 말함
장점
index를 통해 해당 위치에 직접 접근할 수 있기 때문에, 구현이 상대적으로 쉬움
단점
배열 크기가 고정되어 있기 때문에, 데이터 수 변화에 따른 유연성이 부족
삽입, 삭제 시 데이터가 이동해야 하며 평균 배열의 개수/2
리스트 연산
| opertion | desc |
| init() | 리스트 초기화 연산 |
| isEmpty() | 리스트가 비워있는지 확인 |
| isFull() | 리스트가 모두 채워져있는지 확인 |
| getCurrentSize() | 리스트의 크기를 구하는 연산 |
| contains() | 리스트의 지정 위치의 값을 찾는 연산 |
| insert() | 리스트의 지정 위치에 새로운 값을 삽입, 삽입하려는 위치부터 데이터를 뒤로 이동한 후 데이터를 삽입 |
| delete() | 리스트의 지정 위치에 항목을 삭제하는 연산, 삽입하려는 위치로 부터 데이터를 하나씩 앞으로 이동  |
연산을 인터페이스로 구현한. h 파일은 아래와 같다.
linearList.h
#define MAX 100
int itemCount;
int items[MAX];
void init(){
itemCount = 0;
}
int isEmpty(){
if(itemCount == 0)
return 1;
else
return 0;
}
int isFull(){
if(itemCount == MAX)
return 1;
else
return 0;
}
int getCurrentSize(){
return itemCount;
}
int contains(int pos){
return items[pos];
}
int insert(int pos, int item){
int i;
if (isFull() == 0 && pos >=0 && pos <= itemCount){
for (i = itemCount; i> pos; i--)
items[i] = items[i-1];
items[pos] = item;
itemCount = itemCount + 1;
}
else{
printf("List already full and position of insertion is wrong\n");
}
}
int delete(int pos){
int i;
if (isEmpty() == 0 && 0 <= pos && pos < itemCount){
for (i = pos+1; i< itemCount; i++)
items[i-1] = items[i];
itemCount = itemCount -1;
}
else{
printf("List already empty and position of insertion is wrong\n");
}
}
void printList(){
int i;
printf("List contents-----------------\n");
for (i = 0;i<itemCount; i++){
printf("items %d [%d] ", i, items[i]);
}
printf("\n");
}
linearList.c
#include <stdio.h>
#include "linear_list.h"
void main(){
init();
insert(0,10);
printList();
insert(0,20); // index 0번째 위치에 20 값 입력
printList();
insert(1,20); // index 1번째 위치에 20 값 입력, 원래 index 1위치에 있는 10 이 index 2번째로 이동됨
printList();
insert(1,30);
printList();
insert(2,40);
printList();
insert(3,50);
printList();
delete(2);
printList();
delete(2);
printList();
}
List contents-----------------
items 0 [10]
List contents-----------------
items 0 [20] items 1 [10]
List contents-----------------
items 0 [20] items 1 [20] items 2 [10]
List contents-----------------
items 0 [20] items 1 [30] items 2 [20] items 3 [10]
List contents-----------------
items 0 [20] items 1 [30] items 2 [40] items 3 [20] items 4 [10]
List contents-----------------
items 0 [20] items 1 [30] items 2 [40] items 3 [50] items 4 [20] items 5 [10]
List contents-----------------
items 0 [20] items 1 [30] items 2 [50] items 3 [20] items 4 [10]
List contents-----------------
items 0 [20] items 1 [30] items 2 [20] items 3 [10]연결리스트 Linked List
데이터는 메모리 임의의 위치에 저장되고 다음 항목을 가리키는 포인터(링크)를 가짐
포인터와 동적 메모리 할당을 기초로 리스트 자료구조를 구현
데이터와 다음 데이터를 가리키는 포인터가 하나의 Node를 구성
다음 데이터를 가르키는 포인터가 Link의 역할을 함
헤드 포인터가 생성되면 하나의 연결리스트가 생성됨.
장점 : 메모리를 효율적으로 사용할 수 있다.
단점 : 단순 연결 리스트의 경우 마지막 노드를 찾을 때 리스트를 따라 쭉 가야 하므로 데이터 양이 방대 해 질 경우 효율적이지 못할 수 있다.
연결 리스트 Linked List 종류
| 단순 연결리스트 | 하나의 노드에 하나의 링크가 있는 형태 일반적으로 연결리스트라고 하면 단순 연결리스트를 지칭 |
| 이중 연결리스트 | 하나의 노드에 두 개의 링크가 존재 다음 노드뿐만 아니라 이전 노드도 쉽게 찾는게 가능 |
| 원형 연결리스트 | 마지막 노드의 링크가 리스트의 처음 노드를 가리킴 원형 구조로 순환 검색이 가능 |
| 이중 원형 연결리스트 | 가장 복잡한 형태 원형 연결리스트와 이중 연결리스트를 결합한 구조 |
| 배열 Linear List | 연결리스트 Linked List | |
| 공간 | 미리 최대 아이템 수를 예상하고 선언 | 필요한 만큼의 노드만 동적으로 활용 |
| 검색 | index를 이용하기 때문에 검색시간이 짧음 | 포인터를 계속 링크를 따라 가야하므로 검색시간이 걸림 |
| 삽입/ 삭제 | 나머지 요소들이 이동해서 복사되어야 해서 시간이 오래 걸림 | 한 두 번의 포인터 조작만으로 가능하므로 배열보다 유리 |
1부터 100까지의 정수중 임의의 수 10개를 입력받은 후 이를 순서대로 정렬해서 화면에 출력해주는 프로그램을 작성할 때 필요한 자료구조: 선형 리스트 - 배열을 사용해야 함
단순 연결 리스트 기본 연산
| opertion | desc |
| init() | 리스트 초기화 연산 |
| isEmpty() | 리스트가 비워있는지 확인 |
| isFull() | 리스트가 모두 채워져있는지 확인 |
| getCurrentSize() | 리스트의 크기를 구하는 연산 |
| contains() | 리스트의 지정 위치의 값을 찾는 연산 |
| insertNext() | 리스트의 지정된 노드 다음에 새로운 노드를 삽입 |
| insertFirst() | 리스트의 맨 앞에 새로운 노드를 추가하는 함수 |
| insertLast() | 리스트의 맨 뒤에 새로운 노드를 추가하는 함수 |
| removeNext() | 리스트의 지정된 노드가 가리키는 노드를 삭제 |
| printList() | 리스트 내용을 출력 |
노드 타입 선언
노드는 구조체로 선언하고, 이를 포인터로 연결
self referential structure이며 노드 데이터와 링크로 구성
노드 생성 방법
정적 변수
고정된 크기의 메모리가 할당됨
#include <stdio.h>
typedef struct Node{
char item;
struct Node* next;
}nodeType;
void main(){
nodeType n1, n2, n3;
nodeType *head;
n1.item = 'A';
n2.item = 'B';
n3.item = 'C';
n1.next = NULL;
n2.next = NULL;
n3.next = NULL;
head = &n1;
n1.next = &n2;
n2.next = &n3;
}
동적 할당
프로그램 실행 중에 노드 생성에 필요한 메모리 할당
##include <stdio.h>
#include <stdlib.h>
typedef struct Node{
char item;
struct Node* next;
}nodeType;
void printList(nodeType *headPtr)
{
nodeType *p = headPtr;
printf("Start Print Linked List -----------\n");
int i = 0;
for (p = headPtr; p != NULL; p = p->next){
printf("%d 's Node :[%c]\n", i, p ->item);
i++;
}
printf("\n");
}
void main(){
nodeType *head, *temp;
//head 생성 및 1번째 노드 생성
head = (nodeType*)malloc(sizeof(nodeType));
//1번째 값 입력
head ->item = 'A';
printList(head);
// 2번째 노드 생성
head->next = (nodeType*)malloc(sizeof(nodeType));
// 2번째 값 입력
head->next->item = 'B';
printList(head);
// 3번째 노드 생성
head->next->next= (nodeType*)malloc(sizeof(nodeType));
// 3번째 값 입력
head->next->next->item= 'C';
printList(head);
// 마지막 노드 링크 NULL 채우기
head->next->next->next = NULL;
}결괏값
Start Print Linked List -----------
0 's Node :[A]
Start Print Linked List -----------
0 's Node :[A]
1 's Node :[B]
Start Print Linked List -----------
0 's Node :[A]
1 's Node :[B]
2 's Node :[C]
노드 삽입 알고리즘 : insertNext() 함수
1) 삽입할 위치 (앞 노드)를 찾는다 : prevNode = head;
즉 prevNode -> head -> 'A' Node를 가리키고 있음.
2) 메모리에 새로운 노드를 생성하고, 삽입할 데이터를 저장한다.
3) 생성한 노드 링크 값에 앞 노드의 링크 값을 저장한다 = 삽입할 노드의 링크가 삽입될 위치의 다음 노드를 가리키게 한다.
4) 앞 노드의 링크 값이 삽입 노드를 가리키게 한다. = 삽입될 위치의 선행 노드의 링크가 삽입할 노드를 가리키게 한다.
void insertNext(nodeType *prevNode, nodeType *newNode){
if(newNode == NULL){
printf("new Node is NULL. Please use correct insert NODE");
}else{
// newNode = 삽입노드, 삽입노드의 링크가 이전노드의 링크를 가리킴
newNode->next = prevNode->next;
// prevNode = 삽입노드 전의 노드, 이전 노드 링크가 삽입노드를 가리킴
prevNode->next = newNode;
}
}노드 삽입 알고리즘 : insertFirst() 함수
1) 메모리에 새로운 노드를 생성하고, 삽입할 데이터를 저장한다. : newNode
2) 새로운 노드가 가리키는 노드는 기존에 있던 리스트 노드의 헤드가 되어야 한다: newNode->next=headPtr;
3) 새로운 노드를 기존의 리스트 노드에 할당한다(저장한다) , 즉 새로운 노드를 헤드로 만든다. : headPtr=newNode;
void insertFirst(nodeType *headPtr, nodeType *newNode){
// case : head가 null 이므로 현재 리스트에 아무것도 없다는 뜻임
if(headPtr == NULL){
headPtr = newNode;
//case : head 가 존재하는 경우,
}else{
// 새노드가 가지고 있는 다음 노드의 주소값은 헤드의 주소값이 됨 : 왜냐면 앞에서 집어넣으면 기존에 있던 헤드들이 새로운 노드를 기준으로 오른쪽으로 다 밀리기 때문
newNode->next=headPtr;
// 새노드를 head 로 만든다.
headPtr=newNode;
}
}
노드 삽입 알고리즘 : insertLast() 함수
1) 기존에 있던 노드 리스트의 head와 노드들을 새로운 포인터 list가 가르친다.
2) link 가 NULL 인 것을 찾을 때 list 가 노드들을 리스트화 한다
3) 2번 과정에서 맨 마지막 list 노드 link 가 새로운 노드를 포인팅 하게 한다.
void insertLast(nodeType *headPtr, nodeType *newNode){
if(headPtr == NULL){
headPtr = newNode;
}else{
// temporary nodelist에 원래 있던 head 와 list 를 NULL 을 만날 때 까지 집어 넣음
nodeType *list = headPtr;
while(list->next!=NULL)
list = list->next;
// 맨 마지막 노드가 새로운 노드를 가르키게 함
list->next = newNode;
}
}
노드 삭제 알고리즘 : removeNext()
1) 삭제할 노드와 삭제할 노드의 앞 노드를 찾는다
2) 삭제 할 노드의 앞 노드가 삭제할 노드의 다음 노드를 가리키도록 한다
3) 삭제한 노드의 링크를 NULL로 만들어 준다. : 삭제될 노드의 포인터를 이용해서 메모리 해제도 가능하고 , 다른 연결 리스트에 삽입도 가능함.
4) 삭제한 노드를 메모리에 반환한다. : delete 함수
nodeType* removeNext(nodeType *prevNode){
nodeType *removed = prevNode->next;
if (removed != NULL)
prevNode->next = removed->next;
return removed;
}
void delete (nodeType *removedNode){
free(removedNode);
}단순 연결 리스트 예제 1 : 메모리 할당을 MAIN 함수에서 하는 경우
linked_list.h
typedef struct Node{
char item;
struct Node* next;
}nodeType;
void init(nodeType *headPtr){
headPtr = NULL;
}
int isEmpty(nodeType *headPtr){
if(headPtr == NULL)
return 1;
else
return 0;
}
int getCurrentSize(nodeType *headPtr){
nodeType *p;
int count = 0;
for (p=headPtr; p!=NULL; p=p->next)
count = count+1;
return count;
}
char contains(nodeType *headPtr, int pos){
nodeType *p = headPtr;
int i;
for (i=0; i<pos; p=p->next)
if(p == NULL){
return NULL;
}
return p->item;
}
void insertNext(nodeType *prevNode, nodeType *newNode){
if(newNode == NULL){
printf("new Node is NULL. Please use correct insert NODE");
}else{
// newNode = 삽입노드, 삽입노드의 링크가 이전노드의 링크를 가리킴
newNode->next = prevNode->next;
// prevNode = 삽입노드 전의 노드, 이전 노드 링크가 삽입노드를 가리킴
prevNode->next = newNode;
}
}
void insertFirst(nodeType *headPtr, nodeType *newNode){
// case : head가 null 이므로 현재 리스트에 아무것도 없다는 뜻임
if(headPtr == NULL){
headPtr = newNode;
//case : head 가 존재하는 경우,
}else{
// 새노드가 가지고 있는 다음 노드의 주소값은 헤드의 주소값이 됨 : 왜냐면 앞에서 집어넣으면 기존에 있던 헤드들이 새로운 노드를 기준으로 오른쪽으로 다 밀리기 때문
newNode->next=headPtr;
// 새노드를 head 로 만든다.
headPtr=newNode;
}
}
void insertLast(nodeType *headPtr, nodeType *newNode){
if(headPtr == NULL){
headPtr = newNode;
}else{
// temporary nodelist에 원래 있던 head 와 list 를 NULL 을 만날 때 까지 집어 넣음
nodeType *list = headPtr;
while(list->next!=NULL)
list = list->next;
// 맨 마지막 노드가 새로운 노드를 가르키게 함
list->next = newNode;
}
}
nodeType* removeNext(nodeType *prevNode){
nodeType *removed = prevNode->next;
if (removed != NULL)
prevNode->next = removed->next;
return removed;
}
void delete (nodeType *removedNode){
free(removedNode);
}
void printList(nodeType *headPtr)
{
nodeType *p = headPtr;
printf("Start Print Linked List -----------\n");
int i = 0;
for (p = headPtr; p != NULL; p = p->next){
printf("%d 's Node :[%c]\n", i, p ->item);
i++;
}
printf("\n");
}linked_list.c
#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"
void main(){
nodeType *head, *temp;
//메모리 할당을 메인함수에서 하는 케이스
temp = (nodeType*)malloc(sizeof(nodeType));
temp -> item = 'A';
printList(temp);
//Start Print Linked List -----------
//0 's Node :[A]
temp->next = NULL;
head = temp;
printf("temp -----------------------------\n");
printList(temp);
//temp -----------------------------
//Start Print Linked List -----------
//0 's Node :[A]
printf("head -----------------------------\n");
printList(head);
//head -----------------------------
//Start Print Linked List -----------
//0 's Node :[A]
temp = (nodeType*)malloc(sizeof(nodeType));
temp->item = 'B';
printList(temp);
//Start Print Linked List -----------
//0 's Node :[B]
temp->next = NULL;
// void insertNext(nodeType *prevNode, nodeType *newNode)
insertLast(head,temp);
printf("temp -----------------------------\n");
printList(temp);
//temp -----------------------------
//Start Print Linked List -----------
//0 's Node :[B]
printf("head -----------------------------\n");
printList(head);
//head -----------------------------
//Start Print Linked List -----------
//0 's Node :[A]
//1 's Node :[B]
temp = (nodeType*)malloc(sizeof(nodeType));
temp->item = 'C';
printList(temp);
//Start Print Linked List -----------
//0 's Node :[C]
temp->next = NULL;
// void insertNext(nodeType *prevNode, nodeType *newNode)
insertNext(head,temp);
printf("temp -----------------------------\n");
//temp -----------------------------
//Start Print Linked List -----------
//0 's Node :[C]
//1 's Node :[B]
printList(temp);
printf("head -----------------------------\n");
printList(head);
//head -----------------------------
//Start Print Linked List -----------
//0 's Node :[A]
//1 's Node :[C]
//2 's Node :[B]
nodeType *removed1 =removeNext(head);
delete(removed1);
printf("temp -----------------------------\n");
printList(temp);
//temp -----------------------------
//Start Print Linked List -----------
//0 's Node :[]
//1 's Node :[B]
printf("head -----------------------------\n");
printList(head);
//head -----------------------------
//Start Print Linked List -----------
//0 's Node :[A]
//1 's Node :[B]
nodeType *removed2 = removeNext(head);
delete(removed2);
printf("temp -----------------------------\n");
printList(temp);
//temp -----------------------------
//Start Print Linked List -----------
//0 's Node :[]
//1 's Node :[�]
printf("head -----------------------------\n");
printList(head);
//head -----------------------------
//Start Print Linked List -----------
//0 's Node :[A]
}
단순연결 리스트 예제 2 : 메모리 할당을 인터페이스(. h)에서 미리 정의
linked_list 2.h
// 연결리스트의 노드 구조 정의
typedef struct Node{
char item;
struct Node* next;
}nodeType;
// 연결리스트의 헤드 노드 구조 정의 : 연결 리스트의 맨 앞은 일반적으로 '헤드 노드'라고 불리며 연결 리스트의 첫 번째 노드를 가리키는 역할을 한다. 헤드 노드는 데이터 필드가 필요 없고 첫 번째 노드를 가리키기 위한 링크 필드만 필요하므로 listNode형 포인터로 정의한다.
typedef struct{
nodeType* head;
}headNode;
headNode* createLinkedList(){
headNode *H;
//Q? 왜 headNode에는 * 이 붙음?
H = (headNode*)malloc(sizeof(headNode));
H -> head = NULL;
return H;
}
void printList(nodeType *headPtr)
{
nodeType *p = headPtr;
printf("Start Print Linked List -----------\n");
int i = 0;
for (p = headPtr; p != NULL; p = p->next){
printf("%d 's Node :[%c]\n", i, p ->item);
i++;
}
printf("\n");
}
void addNodeFirst(headNode* H, char x){
// newNode : 삽입할 노드
// lastNode : 기존에 있던 리스트
nodeType *newNode;
// 삽입할 노드에 메모리 할당
newNode = (nodeType*)malloc(sizeof(nodeType));
// 삽입할 노드에 value 저장
newNode ->item = x;
newNode ->next = NULL;
if (H->head == NULL){
H->head = newNode;
}else{
newNode->next=H->head;
// 새노드를 head 로 만든다.
H->head = newNode;
}
printList(newNode);
}
void addNodeLast(headNode* H, char x){
// newNode : 삽입할 노드
// lastNode : 기존에 있던 리스트
nodeType *newNode, *lastNode;
// 삽입할 노드에 메모리 할당
newNode = (nodeType*)malloc(sizeof(nodeType));
// 삽입할 노드에 value 저장
newNode ->item = x;
newNode ->next = NULL;
//현재 리스트가 공백인 경우
if (H->head == NULL){
H->head = newNode;
}else{
//현재 있는 노드 리스트(lastNode)를 헤드가 가르키게 하고 lastNode 의 링크가 Null 이 있을 때 까지 lastNode 에 저장.( NULL 이라는 소리는 마지막 리스트 노드까지 가지고 오겠다는 소리)
lastNode = H->head;
while(lastNode->next != NULL )
lastNode = lastNode->next;
// lastNode 의 마지막 링크가 추가할 노드를 가르키게 함.
lastNode->next = newNode;
}
printList(newNode);
printList(lastNode);
}
// 특정한 위치에 노드 삽입
void addNodePos(headNode* H, nodeType* prevNode, char x) {
// 삽입할 노드를 생성하고 메모리할당 및 item 데이터를 할당
nodeType* newNode;
newNode = (nodeType*)malloc(sizeof(nodeType));
newNode -> item = x;
newNode -> next = NULL;
// 삽입할 노드의 다음 노드를 삽입할 노드 이전 노드의 다음노드를 가리키게 함
newNode -> next = prevNode -> next;
// 이전 노드의 다음 노드가 삽입할 노드가 되게 포인팅함
prevNode -> next = newNode;
printList(newNode);
}
// 맨 마지막에 있는 노드 삭제
void deleteLastNode(headNode* H) {
// 삭제할 노드의 앞 노드를 가리킴
nodeType* prevNode;
// 삭제할 노드
nodeType* delNode;
//빈 리스트인 경우 삭제할 노드가 없으므로 종료
if(H -> head == NULL)
return;
//리스트에 노드가 한 개인 경우, 해당 노드를 삭제한다.
if(H -> head -> next == NULL) {
free(H -> head); //그 노드의 메모리를 heap에 반환하고 NULL 을 할당
H -> head = NULL;
return; //프로그램종료
}
//리스트에 노드가 2개 이상인 경우
else {
// 삭제할 노드의 앞노드 : 리스트 에서 첫번째 노드
prevNode = H -> head;
// 삭제할 노드 : 리스트에서 두번째 노드로 저장
delNode = H -> head -> next;
//삭제될 노드를 기준으로 그 뒤에 오는 노드들의 링크가 NULL 즉, 마지막 노드가 될 때 까지 삭제할 노드의 앞노드와 삭제할 노드를 뒤로 한칸 씩 이동시킨다.
while(delNode -> next != NULL) {
prevNode = delNode;
delNode = delNode -> next;
}
// 삭제할 노드가 리스트의 맨 마지막 위치에 있을 때, 이 메모리를 해제한다.
free(delNode);
// 삭제할 노드의 앞노드의 링크에 NULL 할당해서, 삭제할 노드의 앞노드가 리스트의 마지막임을 명시해 줘야한다.
prevNode -> next = NULL;
}
}
// 특정 위치에 있는 노드 삭제
void deleteItNode(headNode* H, nodeType* prevNode, nodeType* delNode) {
// 삭제 할 노드의 선행노드가 삭제할 노드의 다음 노드가 가리키게 함
prevNode -> next = delNode -> next;
// 삭제할 노드의 메모리를 해제함
free(delNode);
return;
}
// 특정노드 검색
//item 값이 x인 노드 검색
void searchNode(headNode* H,char x) {
nodeType* tempNode;
tempNode = H -> head;
while(tempNode -> item != x) {
tempNode = tempNode -> next;
}
printf("Search Successful.\n");
printList(tempNode);
}
linked_list 2.c
#include <stdio.h>
#include <stdlib.h>
#include "linked_list2.h"
void main(){
headNode *headnode = createLinkedList();
printf("First Insert=======================\n");
addNodeFirst(headnode,'A');
printf("Second Insert======================\n");
addNodeLast(headnode,'B');
printf("Third Insert=======================\n");
addNodeFirst(headnode,'C');
/*
Start Print Linked List -----------
0 's Node :[A]
Second Insert=====================
Start Print Linked List -----------
0 's Node :[B]
Start Print Linked List -----------
0 's Node :[A]
1 's Node :[B]
Third Insert=====================
Start Print Linked List -----------
0 's Node :[C]
1 's Node :[A]
2 's Node :[B]
*/
}반응형
'자료구조' 카테고리의 다른 글
| [자료구조 기초] queue , 큐 (0) | 2021.04.14 |
|---|---|
| [자료구조 기초] Stack, 스택 (0) | 2021.04.14 |
| [자료구조 기초] structure, 구조체 (0) | 2021.04.13 |
| [ 자료구초 기초] Array, 배열 (0) | 2021.04.13 |
| [자료구조 기초] Pointer , 포인터 (0) | 2021.04.13 |