Page 1 of 1

## How to create a basic double linked list Rate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=53161&amp;s=f4a54416a1c440679c8699b591044dbb&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Tomas

Reputation: 1
• Posts: 34
• Joined: 12-June 07

Posted 27 May 2008 - 10:26 AM

Firstly, welcome to my tutorial on double linked lists. In this tutorial i will be showing you an example of my code and how it works. So lets start at the beginning by creating a header file. The code will be explained as in line documentation:

#ifndef LIST_H
#define LIST_H

#include <iostream>

using namespace std;

struct element{				//declaration of a new structure
element* nextel;	  //a pointer to the element structure called nextel. It will hold the address of the next element in the list
element* prevel;	  //a pointer to the element structure called prevel. It will hold the address of the previous element in the list
int data;				  //just the data that each element will hold
};

class list{						//declaration of a new class
public:
static element* NewElement();							 //A function used to create a new element in the list with a return type element*
static element* SearchElement(int searchitem);	 //A function used to search for elements in the list with a return type element*
static element* DeleteElement(int searchitem);	  //A function used to delete elements in the list with a return type element*

private:
static element* FirstEl;	//a pointer to the element structure called FirstEl. It will hold the address of the first element in the list
static element* LastEl;	//a pointer to the element structure called LastEl. It will hold the address of the last element in the list
};

#endif

The above code sets you up to create a double linked list, but we have not ,as of yet, written the functions to control the list. The next piece of code develops the functions to control the list:

#include <iostream>
#include "list.h"

using namespace std;

element* list::FirstEl = NULL;	  //This initialises the static element* 'FirstEl' to NULL
element* list::LastEl = NULL;	  //This initialises the static element* 'LastEl' to NULL
int data = 0;

element* list::NewElement(){
element* currentel;					  //This creates a new pointer to element. This will hold the address of the new element
if (FirstEl == NULL){					 //This checks whether FirstEl is equal to NULL
currentel = new element;	 //This creates the new element and makes currentel equal to it
FirstEl = currentel;			   //This makes FirstEl equal to the new element
LastEl = currentel;			   //This makes LastEl equal to the new element
currentel->nextel =  NULL;   //This makes the new elements, next element equal to NULL
currentel->prevel = NULL;	//This makes the new elements, previous element equal to NULL
currentel->data = data;
data++;
return currentel;
}
if (FirstEl != NULL){					 //This checks whether FirstEl is not equal to NULL
currentel = new element;	//This creates the new element and makes currentel equal to it
currentel->nextel = NULL;   //This makes the new elements, next element equal to NULL
LastEl->nextel = currentel;  //This makes the last elements (in the list), next element equal to the new element
currentel->prevel = LastEl;  //This makes the new elements, previous element equal to the last element in the list
LastEl = currentel;			  //This makes LastEl equal to the new element
currentel->data = data;
data++;
return currentel;
}
return NULL;
}

element* list::SearchElement(int searchitem){  //This traverses through the list, and is realy very simple so doesn't need explaining
element* currentel;
if (FirstEl == NULL){
system("CLS");
cout << "There are no elements in the list\n";
return NULL;
}
if (FirstEl != NULL){
currentel = FirstEl;
while (currentel != NULL){
if (currentel->data == searchitem){
return currentel;
}
else
currentel = currentel->nextel;
}
}
system("CLS");
return NULL;
}

element* list::DeleteElement(int searchitem){					//This function deletes an element anywhere within the list
element* deleteptr;
deleteptr = SearchElement(searchitem);

if (deleteptr == FirstEl && deleteptr == LastEl){		 //This checks the element to be deleted is equal to the fist and last element
FirstEl = NULL;												//This makes FirstEl equal to NULL
LastEl = NULL;												//This makes LastEl equal to NULL
delete deleteptr;											 //This deletes the element from the list
return NULL;
}
if (deleteptr == FirstEl && deleteptr != LastEl){		  //This checks the element to be deleted is equal to the fist but notlast element
FirstEl = deleteptr->nextel;							  //This makes FirstEl equal to the element to be deleted, next element
deleteptr->nextel->prevel = NULL;				   //This makes t next element, previous element equal to NULL
delete deleteptr;											 //This deletes the element from the list
return NULL;
}
if (deleteptr != FirstEl && deleteptr == LastEl){		 //This checks the element to be deleted is equal to the last but notfist element
LastEl = deleteptr->prevel;							 //This makes LastEl equal to the element to be deleted, previous element
deleteptr->prevel->nextel = NULL;				  //This makes t previous element, next element equal to NULL
delete deleteptr;											//This deletes the element from the list
return NULL;
}
if (deleteptr != FirstEl && deleteptr != LastEl){		   //This checks the element to be deleted is equal to the fist and last element
deleteptr->prevel->nextel = deleteptr->nextel; //This statement links the previous element to the next element in the list
deleteptr->nextel->prevel = deleteptr->prevel; //This statement links the next element to the previous element in the list
delete deleteptr;											 //This deletes the element from the list
return NULL;
}

if (deleteptr == NULL){
system("CLS");
cout << "No such item found within the list to delete\n";
}
return NULL;
}

The above code completes this tutorial on linked list and all of the code is free to download and use for you own personal use.

Is This A Good Question/Topic? 0