Shahid Riaz Bhatti

Creating a simple Linked List Data Structure using C++ – Part I

March 05

by afeef 5. March 2009 15:37

Technorati Tags: Data Structures,C++,Linked List,CS301

In this post i am going to show you how to implement a simple Linked List data structure in C++ using Visual Studio 2008. However, you can use your favorite IDE to build this example. You can also check the original post at my blog where complete source code of this post is available.

In simplistic view Linked List is a collection of individual List Nodes interconnected with each Node pointing to the Node ahead of it. So to get us started, we need List Nodes first and then we’ll build Linked List data structure using those.

Fire up your favorite IDE and create a new project and add a header file named Node.h. This header file contains the interface of the Node class. Following is the code for this header file.

#pragma once

  

class Node

{

    public:

        Node(void);

        ~Node(void);

  

        int   get();

        void   set(int   object);

  

        Node   * getNext();

        void   setNext(Node   * nextNode);

  

    private:

        int   object;

        Node   * nextNode;

};

In the code snippet above, first data member is an integer type that will hold the node value and the second data member is a pointer to the next node in the list (Null if this is the last node in the list). Getter and Setter methods for the data members are also defined.

Now create a new class and name it Node.cpp. This will implement the interface defined in the Node.h header file. Following is the code for the Node.cpp.

#include "Node.h"

  

    Node::Node(void){

    }

  

    Node::~Node(void){

    }

    int   Node::get() { 

        return   object; 

    }

  

    void   Node::set(int   object) { 

        this->object   =   object; 

    }

  

    Node   * Node::getNext() { 

        return   nextNode; 

    }

  

    void   Node::setNext(Node   * nextNode) { 

        this->nextNode   =   nextNode; 

    }

To create a linked list of Nodes we have to create a List class. For that create a new header file named List.h and copy the following code snippet into it. Include the Node.h header file created earlier.

#pragma once

#include "Node.h"

class List

{

    public:

        List(void);

        ~List(void);

        void   add (int   addObject);

        int    get();

        bool   next();

        friend void  traverse(List list);

        friend List   addNodes();

        void start();

        void remove();

        int length();

  

    private:

        int      size;

        Node *   headNode;

        Node *   currentNode;

        Node *   lastCurrentNode;

};

In this code snippet there is one data member named size. It will hold the current size of the linked list. A part from that three Node pointer are declared pointing to the Head Node, Current Node and the Last Current Node as their names suggest. Two friend functions are declared namely traverse() and addnodes().In the second part I'll show you the implementation of the List class and i'll finish with testing the Linked List in main method

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

Tags:

C++

E-mail | Kick it! | DZone it! | del.icio.us

Permalink | Comments (10) | Post RSS RSS comment feed

Creating a simple Linked List Data Structure using C++ – Part II

March 05

by afeef 5. March 2009 15:30

Technorati Tags: Data Structures,C++,Linked List,CS301

Please read the first part of this topic if you haven't done already. Implement the List class interface by creating a new file named List.cpp. Add the following code to the newly created file. Download the complete source of this example from here.

#include "List.h"

#include <iostream>

  

using namespace std;

List::List(void){

    headNode   =   new Node();

    headNode->setNext(0);

    currentNode   =   0;

    lastCurrentNode  =   0;

    size   =   0;

}

  

List::~List(void)

{

}

  

void   List::add (int  addObject) 

{

    Node *   newNode   =   new   Node();

    newNode->set(addObject);

    if( currentNode   !=   0 )

    {

        newNode->setNext(currentNode->getNext());

        currentNode->setNext( newNode );

        lastCurrentNode   =   currentNode;

        currentNode   =   newNode;

    }

     else

    {

  

        newNode->setNext(0);

        headNode->setNext(newNode);

        lastCurrentNode   =   headNode;

        currentNode   =   newNode;

    }

    size ++;

}

  

/* get() class method */

int   List::get() 

{ 

    if (currentNode  !=  0) 

     return   currentNode->get(); 

}

  

/* next() class method */

bool   List::next() 

{

    if (currentNode  ==  0)   

        return  false;

  

    lastCurrentNode  =  currentNode;

    currentNode  =  currentNode->getNext();

    if (currentNode == 0 || size == 0) 

        return  false;

    else

        return  true;

}

  

/* Friend function to traverse linked list */

void traverse(List list)

{

    Node* savedCurrentNode  =  list.currentNode;

    list.currentNode  =  list.headNode;

    

    for(int i = 1; list.next(); i++)

    {

        cout << "\n Element " << i << "   " << list.get();

    }

    list.currentNode  =  savedCurrentNode;

}

  

/* Friend function to add Nodes into the list */ 

List addNodes()

{

    List   list;

    list.add(2);

    list.add(6);

    list.add(8); 

    list.add(7);   

    list.add(1);

    cout  <<  "\n List size = "  <<  list.size  <<'\n';         

    return  list;

}

  

void List::start() {

    lastCurrentNode = headNode;

    currentNode = headNode;

}

  

void List::remove() {

     if( currentNode != NULL && currentNode != headNode) {

         lastCurrentNode->setNext(currentNode->getNext());

         delete currentNode;

         currentNode = lastCurrentNode->getNext();

         size--;

     }

}

  

int List::length() 

{ 

    return size; 

}

The traverse() friend function traverses the list from start to finish and output the elements contained in the list. The addnodes() friend fuction adds the Nodes to the List. the start() method sets the currentNode pointer to the start of the List. remove() method removes the currentNode from the list. The length() method returns the current size of the Linked list.

Create a main.cpp file to test the Linked List data structure we have created.

#include<iostream>

#include "List.h"

  

using namespace std;

  

int main(){

  

    List list;  // creating a list object

    

    // adding values to the list

    list.add(5); 

    list.add(13); 

    list.add(4);

    list.add(8); 

    list.add(24); 

    list.add(48); 

    list.add(12);

  

    // calling the start method of the list

    list.start();

  

    // printing all the elements of the list

    while (list.next()) 

        cout << "List Element: "<< list.get()<<endl;

  

    return 0;

  

}

Happy programming …!!!

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

Tags:

C++

E-mail | Kick it! | DZone it! | del.icio.us

Permalink | Comments (9) | Post RSS RSS comment feed

ASP.Net Client Call BackComments: 92Rating: 5 / 1
Javascript Numeric Text BoxComments: 13Rating: 5 / 1
Set IFrame Src using JQueryComments: 7Rating: 0 / 0
Sharepont Event HandlerComments: 18Rating: 0 / 0
.Net Properties Question asked and my AnswerComments: 14Rating: 0 / 0
A Question from a reader and my AnswerComments: 19Rating: 0 / 0
Read data from SharePoint ListComments: 25Rating: 0 / 0
Insert Data in Sharepoint List using Sharepoint object modelComments: 54Rating: 0 / 0
GO: Google Launches Its Own Programming LanguageComments: 12Rating: 0 / 0
How to show div tags on top of a flash movieComments: 14Rating: 5 / 1

RecentComments

iframe source on the fly (31)
look4wholesaler wrote: wholesale nike shox air max wholesale air max… [More]
How to show div tags on top of a flash movie (14)
Online Penny Auctions wrote: I just want to let you know that I just check out… [More]
Stop cyber war between India and Pakistan.. (16)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
Insert Data in Sharepoint List using Sharepoint object model (54)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
How to Remove command bar button from Add-Ins (13)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
How to Implement Shallow copy in .Net (14)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
Read data from SharePoint List (25)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
Sharepont Event Handler (18)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
Delegate in C Sharp (15)
puma speed cat trainers wrote: This valuable editorial was very useful to read, … [More]
ASP.Net Client Call Back (92)
Homes for sale wrote: A durable rubber outsole offers lightweight suppor… [More]

Comment RSS