이중 링크드 리스트(Doubly Linked List)

• 이중 링크드 리스트 기본 구조

-노드는 정보(Data) & 다음 노드(Next)가 누구인지  & 이전 노드가(Prev) 누구인지 저장하고 있다.

-제일 앞의 노드(Head)와 제일 뒤의 노드(End)를 연결 시키면 원형 링크드 리스트가 된다.

• 단일 링크드 리스트와의 차이

-이중 링크드 리스트는 전 노드에 접근 가능하다는 장점이 있다.

        typedef struct _Node {

               char Data;

               struct _Node *Next;

               struct _Node *Prev;

        }NODE;

• 이중 링크드 리스트 삽입

삽입할 노드가 들어갈 위치를 찾고,

노드#01의 다음노드(Next) = 삽입노드

삽입 노드의 전 노드(Prev) = 노드#01

삽입 노드의 다음노드(Next) = 노드#02

노드#02의 전 노드(Prev) = 삽입노드

삽입 종료

void DoublyLinkedList::Insert(char data)

{

        // 최초 검색 노드를 헤더로 설정

        NODE* indexNode = m_head;

 

        //현재 노드의 NEXT가 end노드면 반복문 중단

        for (indexNode; indexNode->Next != m_end; indexNode = indexNode->Next)

        {

               if (indexNode->Next->Data > data)

                       break;

        }

 

        //##중복된 데이터 삽입 금지##

        if (indexNode->Data == data)

               return;

 

        //새로운 노드 생성

        NODE* newNode = new NODE();

 

        //새 노드에 데이터 저장

        newNode->Data = data;

        newNode->Prev = indexNode;

        newNode->Next = indexNode->Next;

 

        //현재 노드의 Next와 Next의 Prev로 새 노드를 할당

        indexNode->Next->Prev = newNode;

        indexNode->Next = newNode;

}

• 이중 링크드 리스트 삭제

이중 링크드 리스트의 삭제는

삭제할 노드의 앞뒤를 연결 시킨 후, 삭제할 노드를 삭제하면 된다.

단일 링크드 리스트와 다른 점이라면, 뒷노드의 Prev(전 노드)도 신경 써야 한다는 점이다.

삭제할 노드를 찾고,

삭제할 노드의 앞노드(삭제 노드의 Prev) : 노드#01

삭제할 노드의 다음 노드(삭제 노드의 Next) : 노드#02

[노드#01과 노드#02를 연결]

노드#01의 다음 노드(Next) = 노드#02

노드#02의 전 노드(Prev) = 노드#01

앞뒤 노드 연결이 완료되면,

노드를 삭제하면 된다.

void DoublyLinkedList::Delete(char data)

{

        //최초 검색 노드를 헤더의 Next로 설정

        NODE* deleteNode = m_head->Next;

 

        //현재 노드의  데이터가, 입력받은 데이터와 같다면 반복중단

        for (deleteNode; deleteNode != m_end; deleteNode = deleteNode->Next)

        {

               if (deleteNode->Data == data)

                       break;

        }

 

        //현재 리스트에 입력받은 데이터가 없다면 함수 중단

        if (deleteNode == m_end)

               return;

 

        //삭제할 노드의 전/후 노드 연결

        deleteNode->Next->Prev = deleteNode->Prev;

        deleteNode->Prev->Next = deleteNode->Next;

 

        //노드 삭제

        delete(deleteNode);

}

• 전체 코드

#pragma once

class DoublyLinkedList

{

private:

        typedef struct _Node {

               char Data;

               struct _Node *Next;

               struct _Node *Prev;

        }NODE;

 

private:

        NODE *m_head, *m_end;

 

public:

        DoublyLinkedList();

        ~DoublyLinkedList();  

 

        void Insert(char data);

        void Delete(char data);

        void Print();

};

#include "stdafx.h"

#include "DoublyLinkedList.h"

 

 

DoublyLinkedList::DoublyLinkedList()

{

        //초기화

        m_head = new NODE();

        m_end = new NODE();

 

        //헤드 세팅

        m_head->Prev = NULL;

        m_head->Next = m_end;

 

        //엔드 세팅

        m_end->Prev = m_head;

        m_end->Next = m_end;

}

 

 

DoublyLinkedList::~DoublyLinkedList()

{

}

 

void DoublyLinkedList::Insert(char data)

{

        // 최초 검색 노드를 헤더로 설정

        NODE* indexNode = m_head;

 

        //현재 노드의 NEXT가 end노드면 반복문 중단

        for (indexNode; indexNode->Next != m_end; indexNode = indexNode->Next)

        {

               if (indexNode->Next->Data > data)

                       break;

        }

 

        //##중복된 데이터 삽입 금지##

        if (indexNode->Data == data)

               return;

 

        //새로운 노드 생성

        NODE* newNode = new NODE();

 

        //새 노드에 데이터 저장

        newNode->Data = data;

        newNode->Prev = indexNode;

        newNode->Next = indexNode->Next;

 

        //현재 노드의 Next와 Next의 Prev로 새 노드를 할당

        indexNode->Next->Prev = newNode;

        indexNode->Next = newNode;

}

 

void DoublyLinkedList::Delete(char data)

{

        //최초 검색 노드를 헤더의 Next로 설정

        NODE* deleteNode = m_head->Next;

 

        //현재 노드의  데이터가, 입력받은 데이터와 같다면 반복중단

        for (deleteNode; deleteNode != m_end; deleteNode = deleteNode->Next)

        {

               if (deleteNode->Data == data)

                       break;

        }

 

        //현재 리스트에 입력받은 데이터가 없다면 함수 중단

        if (deleteNode == m_end)

               return;

 

        //삭제할 노드의 전/후 노드 연결

        deleteNode->Next->Prev = deleteNode->Prev;

        deleteNode->Prev->Next = deleteNode->Next;

 

        //노드 삭제

        delete(deleteNode);

}

 

void DoublyLinkedList::Print()

{

        NODE* indexNode = m_head->Next;

 

        for (indexNode; indexNode != m_end; indexNode = indexNode->Next)

        {

               printf("%c ", indexNode->Data);

        }

        printf("\n");

}