Learn Computer Science programming - C# and C++ Algorithms

 
Double Linked List C++ (Doubly-Linked List)
A doubly-linked list is a linked data structure that consists of a set of data records that contain references to the previous and to the next record.

The code below implements a doubly-linked list as well as offering the feature to convert it to a cyclic linked list which simply links the head and tail together.
Picture
Code
doublelinkedlist.zip
File Size: 2953 kb
File Type: zip
Download File


#include <iostream>
#include "Classes.h"
using namespace std;


void DLinkedList::AddItem (int d)
{
DLink *newItem = new DLink;

if (pHead) // To avoid NULLs in the first item only
pHead->Prev = newItem;


if (!pTail) // Setup a pointer on the tail
pTail = newItem;


newItem->Next = pHead;
newItem->Prev = NULL;
newItem->d = d;


pHead = newItem;
cout << "Added element # " << newItem->d << endl;
//delete(newItem); CANNOT DELETE THIS BECAUSE this item was created and therefore will actually delete the NODE
}


void DLinkedList::Display()
{
DLink *current = pHead;
while (current)
{
//Output data for the current DLink
wcout << L"Current DLink data --------------> "  << current->d;


//Identify and comment if this is the pHead DLink - for clarity only
if (current == pHead )
{
wcout << L" -- Head" << endl;
}
else
{
wcout << endl ;
}


// Print Previous and Next links
wcout << L"Prev DLink Address " << current->Prev << endl;
wcout << L"Next DLink Address " << current->Next << endl;

// Print the address of the current node
if (current->Next)
wcout << L"My Address = " << current->Next->Prev  << endl;
else
wcout << L"My Address = " << current->Prev->Next   << endl;


current = current->Next;
}
delete (current);
}


DLink *DLinkedList::FindElement (int value)
{
DLink *myLink = pHead;

wcout << L"I am attempting to find Element # ";


while (myLink)
{
wcout << myLink->d << " , ";
if (myLink->d == value)
{
wcout << L"Found value # " << myLink->d  << endl << endl;
return myLink;
}
myLink = myLink->Next;
}
// No element found
delete (myLink);
return NULL;
}


void DLinkedList::Reverse()
{
DLink* currentItem = pHead;
    DLink* tmp;
pTail = pHead; // Assign head to become new TAIL


    while (currentItem) 
{
tmp = currentItem->Next; //TMP holds the NEXT pointer
currentItem->Next = currentItem->Prev ; // Reverse Next and Prev
currentItem->Prev = tmp ; // Replace Prev


pHead = currentItem; // new Head is current item. This will eventually replace the TAIL
currentItem = currentItem->Prev; // or = tmp. Navigate in opposite direction
}


delete (tmp);
delete (currentItem);
}
void DLinkedList::RemoveItem (DLink *deleteMe)
{
DLink* current = pHead;
// If HEAD is to be deleted
if (pHead == deleteMe)
{
pHead = pHead->Next ;
deleteMe->Next->Prev = NULL;
free(deleteMe);
return;
}


// If TAIL is to be deleted
if (pTail == deleteMe)
{
pTail = pTail->Prev;
deleteMe->Prev->Next = NULL;
free(deleteMe);
return;
}


// If deleting other nodes 
deleteMe->Prev->Next = deleteMe->Next ;
deleteMe->Next->Prev = deleteMe->Prev;  
free(deleteMe);
}




void DLinkedList::AddToEnd (int d)
{
DLink *newItemEnd = new DLink; // Create a new item of type DLink
newItemEnd->d = d; // Assign the desired value to it
newItemEnd->Next = NULL; // Assign it's DLink to NULL since it will be the last element

newItemEnd->Prev = pTail;
pTail->Next = newItemEnd;
pTail = newItemEnd;


}
void DLinkedList::Swap (DLink *x, DLink *y)
{
DLink *TMPx = new DLink; // Temporary variable to hold values of pointers to X
DLink *TMPy = new DLink; // Temporary variable to hold values of pointers to Y


//In the case of Heads or Tails, this code assume that HEAD will always be passed
//as X and TAIL will always be passed as Y. To account for the opposite, 
//I will do a check at the begining and swap if necessary. 
//This will save many lines of code and additional complexity.
if (y==pHead || x==pTail) // Swap X & Y
{
DLink * TMP = new DLink;
TMP = y;
y = x;
x=TMP;
}


//Hold the references to both X & Y from other nodes in a temp variable
TMPx->Prev = x->Prev; 
TMPx->Next = x->Next; 
TMPy->Prev = y->Prev; 
TMPy->Next = y->Next;


// Modify LEFT node pointing to X. NOT necessary if X is Head
if (x!=pHead) // or (x->Prev) // Head
x->Prev->Next = y;
else
pHead = y;

// Modify RIGHT node pointing to Y. NOT necessary if Y is Tail
if (y!=pTail) // or (y->Next) // Tail
y->Next->Prev = x;
else
pTail = x;


// Swap Content of both X & Y. *** AS IS *** NOT Neighbors ***
if (TMPx->Next != y && TMPy->Prev != x)
{
x->Next->Prev = y; 
y->Prev->Next = x;


x->Next = TMPy->Next;
y->Prev = TMPx->Prev;
x->Prev = TMPy->Prev; 
y->Next = TMPx->Next;
}
else // If Neighbors
{
x->Next = TMPy->Next;
y->Prev = TMPx->Prev;
x->Prev = y;
y->Next = x;
}
}
void DLinkedList::Append (DLink *AfterMe, int d)
{
if (!pHead || !AfterMe) // If LL is empty
return;
DLink * current = pHead;
DLink *newItem = new DLink;


newItem->d = d;


while (current)
{
if (current == AfterMe)
{
//Found location needed to insert item after.
//Assign new item links
newItem->Prev = current;
newItem->Next = current->Next;
// Assign Current item's link to newItem
current->Next = newItem;
// Assign Next item's link to newItem
current->Next->Prev = newItem;
}

current = current->Next;
}
delete (current);
}
void DLinkedList::Sort ()
{
int tmp;
DLink *current = new DLink;
DLink *currentNext = new DLink;


current = pHead;
currentNext = pHead->Next;


while (current && currentNext)
{
while (currentNext)
{
if (current->d  > currentNext->d ) 
{
tmp = currentNext->d;
currentNext->d = current->d;
current->d = tmp;
}
currentNext = currentNext->Next;


}
current = current->Next;
currentNext = current->Next;
}
}


int DLinkedList::IsCyclic ()
{
DLink *SP, *FP;
SP = FP = pHead;

if (FP->Next->Next)
FP = FP->Next->Next;

while (1)
{
if (!FP || !FP->Next)
return 0;
else if (SP == FP || SP == FP->Next)
return 1;
else
{
SP = SP->Next ;
FP = FP->Next->Next; 
}
}
}
void DLinkedList::MakeCyclic ()
{
wcout << "Made this linked list cyclic. Pointed pTail->next = pHead";
pTail->Next = pHead;
}
void DLinkedList::MakeNOTCyclic ()
{
wcout << "Made this linked list NOT cyclic. Pointed pTail->next = NULL";
pTail->Next = NULL;}