안녕하세요 c++ 공부하고있는 대학생입니다.
이번에는 저번에 올린 이중 원형 연결리스트가 아닌, 이중 연결 리스트를 구현 해 보았습니다.
원리는 저번에 올린것과 비슷하게 노드를 연결 했습니다.
#include <stdio.h>
#include <stdlib.h>사용 한 헤더입니다. stdio는 입출력을 위한 헤더이고, stdlib는 동적할당하기 위해 추가한 헤더입니다.
typedef struct node {
struct node *next;
struct node *prev;
int data;
}node;
typedef struct List {
struct node *head;
int count;
}List;이번에는 헤드노드 하나로 만들었습니다.
List *createinit() {
List *list = (List *)malloc(sizeof(List));
if(list->head == NULL) {
printf("err\n");
}
else {
list->head = NULL;
list->count = 0;
}
printf("success createinit\n");
return list;
}list 에 대한 init 함수입니다.
void pushdata(List *list,int countlist, int data) {
node *newNode = (node *)malloc(sizeof(node));
node *preNode = list->head;
newNode->data = data;
if(list->count == 0) {
list->head = newNode;
list->head->next = newNode;
newNode->prev = list->head;
list->count++;
}
else {
for(int i =0; i<countlist; i++) {
preNode = preNode->prev;
}
newNode->next = preNode->next;
newNode->prev = preNode;
preNode->next = newNode;
newNode->next->prev = newNode;
list->count++;
}
printf("success pushdata\n");
}데이터를 넣는 함수입니다. list->count가 0일시에, list->head 와 newNode간의 관계를 만들어주었고,
else 문에서 이전노드를 가리키기 위해, preNode로 선언해서 옮겨서 데이터를 삽입하였습니다.
void delnode(List *list,int index) {
// printf("count : %d\n",list->count);
if(list->count <index) {
printf("del err\n");
return;
}
node *delNode = list->head;
if(list->count == 0) {
printf("none delete node\n");
}
else {
for(int i =list->count; i>1; i--) {
delNode = delNode->prev;
printf("[cat : %d ] \n",delNode->data);
}
delNode->prev->next = delNode->next;
delNode->next->prev = delNode->prev;
free(delNode);
list->count--;
}
}삭제부분입니다. list->count가 삭제하고자 하는 index보다 값이 작으면, err문을 띄워 예외를 처리하였습니다.
for문안에 cat : %d 를 띄워서 어떤인덱스를 삭제하고, 어떤인덱스가 남아있는지 체크하기위해 만들었으며, 삽입부분이 tail부분에서 삽입하도록 하였기때문에, head점을 잡아주기위해 delNode = delNode->prev로 옮겨가는 과정입니다.
그리고 삭제할 노드가 연결되있는 이전노드와 다음노드를 서로 연결해서 free로 반환해주었습니다.
void search(List *list, int num) {
node *curNode = list->head;
int cat = 0;
int i;
for(i = list->count, curNode = list->head; i>0; i--, curNode = curNode->next) {
if(curNode->data == num) {
printf("find index : %d \n",i);
cat++;
}
}
if(cat == 0) {
printf("not found index\n");
return;
}
}검색부분입니다. curNode를 헤드로 가리켜주고, next함으로써 해당 원하는 값이 있는 인덱스를 찾기위한 코드입니다.
void print(List *list) {
printf("test : %d\n",list->head->data);
int i;
node *curNode;
for(i = list->count, curNode = list->head; i > 0; i--,curNode = curNode->prev) {
printf("[ %d ] ",curNode->data);
}
}
void reverse(List *list) {
int i;
node *curNode;
for(i = list->count, curNode = list->head->next; i > 0; i--,curNode = curNode->next) {
printf("[ %d ] ",curNode->data);
}
}출력부분입니다.
void clear(List *list) {
printf("count : %d\n",list->count);
node *clearNode = list->head;
if(list->count == 0) {
printf("none clear node\n");
}
else {
for(int i =list->count; i>1; i--) {
clearNode = clearNode->prev;
}
clearNode->prev->next = clearNode->next;
clearNode->next->prev = clearNode->prev;
free(clearNode);
list->count--;
countlist = list->count;
if(list->count >0) return clear(list);
}
}모두 초기화시켜버리는 clear함수입니다.
삭제함수랑 비슷하지만, 재귀를 통해서 모두 한번에 삭제 될 수 있도록 구현하였습니다.
마지막으로 전체코드를 보여드리며, 마무리하겠습니다.
#include <stdio.h>
#include <stdlib.h>
int countlist = 0;
typedef struct node {
struct node *next;
struct node *prev;
int data;
}node;
typedef struct List {
struct node *head;
int count;
}List;
List *createinit() {
List *list = (List *)malloc(sizeof(List));
if(list->head == NULL) {
printf("err\n");
}
else {
list->head = NULL;
list->count = 0;
}
printf("success createinit\n");
return list;
}
void pushdata(List *list,int countlist, int data) {
node *newNode = (node *)malloc(sizeof(node));
node *preNode = list->head;
newNode->data = data;
if(list->count == 0) {
list->head = newNode;
list->head->next = newNode;
newNode->prev = list->head;
list->count++;
}
else {
for(int i =0; i<countlist; i++) {
preNode = preNode->prev;
}
newNode->next = preNode->next;
newNode->prev = preNode;
preNode->next = newNode;
newNode->next->prev = newNode;
list->count++;
}
printf("success pushdata\n");
}
void delnode(List *list,int index) {
// printf("count : %d\n",list->count);
if(list->count <index) {
printf("del err\n");
return;
}
node *delNode = list->head;
if(list->count == 0) {
printf("none delete node\n");
}
else {
for(int i =list->count; i>1; i--) {
delNode = delNode->prev;
printf("[cat : %d ] \n",delNode->data);
}
delNode->prev->next = delNode->next;
delNode->next->prev = delNode->prev;
free(delNode);
list->count--;
}
}
void search(List *list, int num) {
node *curNode = list->head;
int cat = 0;
int i;
for(i = list->count, curNode = list->head; i>0; i--, curNode = curNode->next) {
if(curNode->data == num) {
printf("find index : %d \n",i);
cat++;
}
}
if(cat == 0) {
printf("not found index\n");
return;
}
}
void print(List *list) {
printf("test : %d\n",list->head->data);
int i;
node *curNode;
for(i = list->count, curNode = list->head; i > 0; i--,curNode = curNode->prev) {
printf("[ %d ] ",curNode->data);
}
}
void reverse(List *list) {
int i;
node *curNode;
for(i = list->count, curNode = list->head->next; i > 0; i--,curNode = curNode->next) {
printf("[ %d ] ",curNode->data);
}
}
void clear(List *list) {
printf("count : %d\n",list->count);
node *cleaerNode = list->head;
if(list->count == 0) {
printf("none celar node\n");
}
else {
for(int i =list->count; i>1; i--) {
clearNode = clearNode->prev;
}
clearNode->prev->next = clearNode->next;
clearNode->next->prev = clearNode->prev;
free(clearNode);
list->count--;
countlist = list->count;
if(list->count >0) return clear(list);
}
}
int main() {
List *list = createinit();
for(int i =0; i<10; i++) {
pushdata(list,countlist++,i);
countlist++;
}
printf("0\n");
list->count = 0;
print(list);
printf("100\n");
list->count = 10;
print(list);
printf("\n");
search(list,4);
printf("\n\n");
reverse(list);
printf("\n\n");
search(list,4);
printf("\n");
printf("clear\n");
clear(list);
print(list);
printf("countlist : %d\n",countlist);
for(int i =0; i<10; i++) {
pushdata(list,countlist++,i);
countlist++;
}
printf("\n\n");
print(list);
return 0;
}
C++ 공부하고있는 대학생입니다.