How to understand linked list - Learning C++

By Sergey Skudaev

Here you will find a C++ code example for link list. I guarantee that you will understand what link list is and how to write C++ code for link list.. Complete C++ code example is provided. You will learn what is class. What is class member variables, class member functions or member methods?

Let us imaging a puzzle. You have a row of boxes. Each box contains a card with one letter. You have to figure out the sequence of the letters, so that letters would make a word.

On the picture you can see that each box has number on its front side. You may guess that these numbers are the key to the puzzle. The first box has letter T inside and number 5 on the site. Take card with letter T and put aside. The number 5 may point to the next letter. Count boxes. The fifth box has a letter e. Take the card with e letter and place it next to T. You got "Te". The box with letter e has number 2 on its side. So, take the card from 2nd box and place next to "Te". You got. "Tec" The box with letter c has number 10, so take the card from the 10 th box. You got "Tech". The box with letter h has number 4, so take card from 4 th box. You got "Techn". Continue follow the numbers and you will get the whole word: Technology.

That is how linked list works. It is made of nodes. Each node has at least one variable that holds data ( a text or number) and variable (pointer) that holds address of the next node. System walks through node list as you did in the puzzle row. The pointer of the last node has null value or it may point to the first node. Then we have closed linked list.

Below is a code for Node class. For simplicity I created a node that holds integer and node pointer to the next node. Both class member variables declared as private. It is good programing practice not to use global variables, because private members cannot be seen from outside the class. We still need to set and to read these pivate member variables. Public function set and get will do the job

#include<iostream>
#include<stdlib.h>

class Node
{
public:

	     // class constractor

	     Node();
	     Node(int n);
	     virtual ~Node();

	   //public methods and members
   // method assign value to node
   void setData(int n);


   int getData();

   //method to assign next node address
   void setNext(Node *anext);

   //method to get next node
   Node * getNext();

private:

   Node *next;
   int data;

   };


Node.cpp

   Node::Node()
   {
	      data=0;
          next = NULL;
   }

   //constractor to create node with data
   Node::Node (int n)
   {
          data = n;
          next=NULL;
   }

   // destructor
   Node::~Node()
   {
           next=NULL;
   }




   //method assigns value to data
   void Node::setData(int n)
   {
      data=n;
   }

   //method read value from data
   int Node::getData()
   {
      return data;
   }


   //method to assign next node
   void Node::setNext(Node *anode)
   {
      	next=anode;
   }

   Node * Node::getNext()
   {
        return next;
   }

If you want to add a new node to the end of the linked list create a new node. Then point pointer of the last node to the address of the new node and assign null to the new node pointer.

If you want to add a new node to the beginning of the linked list create a new node, Point pointer of the new node to the first node and that is it.

If you need to add a node in the middle of the linked list create a new node, then break the chain: redirect pointer of the previous to the break node to a new node and point pointer of the new node to the next to the break node.

Isn't it simple? Yes. It is.

list.h file declare list member functions or member methods.

#include<iostream>
#include<stdlib.h>
#include "Node.h"

class List
{
public:
	   List();
	   virtual ~List();

	   void makeEmpty();
    	void deleteNode();
       void countNodes(int &count);
       void print();

       void addNodeToEnd();
	   void addToHead();
	   void deleteNode(int item);
	   void insertAfterNode(int item);


private:

	
   Node *head;
	   void recursive_count(int &count, Node *anode);


};

Dowload all the rest files for linked list C++ Programming By Examples

Play with this code, try to write additional member functions. There is always a way to improve the C ++ code. Try to write linked list that sort numbers while adding them. Try to write linked list that holds text.

Hint: Code for a Node that holds text:

class WNode
{
public:

	   void setNext(WNode *anext);

	   WNode* getNext();

	   void setData(char *d);

	   char *getData();

	   WNode();

	   WNode(char *d);

   virtual ~WNode();

private:

	   WNode *next;
	   char *data;

};

My eBooks on Amazon.com