문제05-2 더미 노드 기반의 양방향 연결 리스트 구현
1. 양방향 연결 리스트
2. 더미 노드가 리스트의 앞 뒤에 각각 존재 해야함
3. 포인터 변수 head와 tail이 있어서 리스트의 앞과 뒤를 각각 가리킴.
4. 새노드를 꼬리에 추가하는 방식으로 LInsert 구현
// DlinkedHeader.h
#pragma once;
typedef struct _node
{
int data;
struct _node * next;
struct _node * prev;
}Node;
typedef struct _dlist
{
Node * head;
Node * tail;
Node * cur;
int numOfdata;
} List;
void ListInit(List * plist);
void LInsert(List * plist, int data);
int LFirst(List * plist, int * pdata);
int LNext(List * plist, int * pdata);
int LRemove(List *plist);
int LCount(List *plist);
//DlinkedList.cpp
#include <iostream>
#include "DlinkedHeader.h"
void ListInit(List * plist)
{
plist->head = (Node*)malloc(sizeof(Node));
plist->tail = (Node*)malloc(sizeof(Node));
plist->head->prev = NULL;
plist->head->next = plist->tail;
plist->tail->next = NULL;
plist->tail->prev = plist->head;
plist->cur = NULL;
plist->numOfdata = 0;
}
void LInsert(List * plist, int data)
{
Node * newnode = (Node*)malloc(sizeof(Node));
newnode->data = data;
newnode->prev = plist->tail->prev;
plist->tail->prev->next = newnode;
newnode->next = plist->tail;
plist->tail->prev = newnode;
(plist->numOfdata)++;
}
int LFirst(List * plist, int * pdata)
{
if (plist->head->next == plist->tail)
return false;
plist->cur = plist->head->next;
*pdata = plist->cur->data;
return true;
}
int LNext(List * plist, int * pdata)
{
if (plist->cur->next == plist->tail)
return false;
plist->cur = plist->cur->next;
*pdata = plist->cur->data;
return true;
}
int LRemove(List *plist)
{
Node * temp = plist->cur;
int itemp = temp->data;
plist->cur->prev->next = plist->cur->next;
plist->cur->next->prev = plist->cur->prev;
plist->cur = plist->cur->prev;
free(temp);
(plist->numOfdata)--;
return itemp;
}
int LCount(List *plist)
{
return plist->numOfdata;
}
// Main . cpp
#include <iostream>
#include "DlinkedHeader.h"
using namespace std;
int main()
{
List list;
int data;
ListInit(&list); // 데이터 초기화
LInsert(&list, 1); // 1~8 데이터 저장
LInsert(&list, 2);
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsert(&list, 6);
LInsert(&list, 7);
LInsert(&list, 8);
if (LFirst(&list, &data)) // 데이터 조회
{
cout << data << " ";
while (LNext(&list, &data))
cout << data << " ";
cout << endl;
}
if (LFirst(&list, &data)) // 2의 배수 데이터 삭제
{
if (data % 2 == 0)
LRemove(&list);
while (LNext(&list, &data))
if (data % 2 == 0)
LRemove(&list);
}
if (LFirst(&list, &data)) // 삭제 후 데이터 조회
{
cout << data << " ";
while (LNext(&list, &data))
cout << data << " ";
cout << endl;
}
}
