문제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;

}

}