Page 1 of 1

How to create a basic double linked list Rate Topic: -----

#1 Tomas  Icon User is offline

  • New D.I.C Head
  • member icon

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

Post icon  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");
	cout << searchitem << " was not found in the list\n";
	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
  • +

Replies To: How to create a basic double linked list

#2 Sadaiy  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 107
  • Joined: 03-October 08

Posted 03 October 2008 - 06:57 PM

Fine work but i have a few questions.. Can you add implementation on how to sort the list, a copy constructor for the list, a destructor and a way too add items in order instead of just adding a node at the end ???
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1