Published by
Dec 7, 2013 (last update: Dec 8, 2013)

Linked Lists

Score: 3.6/5 (1099 votes)
*****
A set of items of the same type in which each item points to ("is linked to") the next item in the list. Ordering of items is not part of the definition, therefore, we will not consider the ordering. Yet determined according to the usage.


NOTE: Since sequence of elements is not part of definition of a linked list, many other structures can be implemented using Linked Lists.
E.g. if items are ordered according to the sequence of insertion into the list, this corresponds to a stack, in which the top item is pointed by the list head pointer.

Head pointer

  • List head is a special pointer to the first item in the list.
  • The last node(rear) points to a NULL address
  • In processing a list, any node can only be accessed after having accessed all other nodes before it. This property might also be called, in other words, Strict Sequential Access (SSA).

      • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      		 
      // implementation of LinkedList
// the Node class will be given later
// Author: Ali Selcuk AKYUZ
// Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr
// Electrical and Electronics Engineering Department
// Middle East Technical University - ANKARA
// If any questions please send me an email

#include <iostream>
#include "Node.cpp"
using namespace std;
int main ()
{
  Node<char> *p,*q,*r;
  // Link the nodes with each other
  q = new Node<char>('B'); // here nxtptr is passed by a nullptr by default
  p = new Node<char>('A',q);
  r = new Node<char>('C');

  // modify the list
  q->InsertAfter(r);
  /*
  Call the InsertAfter method that belongs to the object pointed by q, as
  paramater, pass to it the address contained in r.
  */

  cout << "p:" << p->data << endl;                 // "A" will be printed out
  cout << "p_next:" << p->NextNode()->data << endl;  // "B" will be printed out
  cout << "q:" << q->data << endl;                 // "B" will be printed out
  cout << "q_next:" << q->NextNode()->data << endl;  // "C" will be printed out
  cout << "r:" << r->data << endl;                 // "C" will be printed out

  p = p->NextNode(); // p now points to the node coming after the node it was
                     // previously pointing to.
  cout << endl;
  cout << "p:" << p->data << endl;                 // "B" will be printed out

  r = q->DeleteAfter();        // copy to r the address of the node pointed by
  //the node pointed by the node pointed by q, and remove that node from the list

  Node<char> *head;
  head = GetNode('A',GetNode('B',GetNode('C')));
  /*
  Here above method, creates a list which has nodes having data A,B,C and each
  node pointing to the next one respectively.
  */
  delete q;
  delete p;
  delete r;
  return 0;
}

      When we compile and run this program, the screen will show:
      
p:A
P_next:B
q:B
q_next:C
r:C

p:B

      Now let us implement the Node class so that we can have a better understanding of this structure.

      Let me start with the header

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      		 
      // Node.h
// Author: Ali Selcuk AKYUZ
// Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr
// Electrical and Electronics Engineering Department
// Middle East Technical University - ANKARA 
// If any questions please send me an email

#ifndef NODE_H
#define NODE_H
#include <iostream>

using namespace std;

template<class T>
class Node
{
    public:
        Node();
        Node(const T& item, Node<T>* ptrnext = NULL);
        T data;
        // access to the next node
        Node<T>* NextNode();
        // list modification methods
        void InsertAfter(Node<T>* p);
        Node<T>* DeleteAfter();
        Node<T> * GetNode(const T& item, Node<T>* nextptr = NULL);
    private:

        Node<T> * next;
};

#endif // NODE_H


      Here we have a default constructer, and three methods that will be explained later in the cpp part of the class implementation.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      		 
      // implementation of Node class
// Author: Ali Selcuk AKYUZ
// Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr
// Electrical and Electronics Engineering Department
// Middle East Technical University - ANKARA 
// If any questions please send me an email

#include "Node.h"

template<class T>
Node<T>::Node()
{
    // default constructor
    // this is to allow us to create an object without any initialization

}


//  This constructor is just to set next pointer of a node and the data contained.
template<class T>
Node<T>::Node(const T& item,Node<T>* ptrnext)
{
    this->data = item;
    this->next = ptrnext;
}

template<class T>
Node<T>*Node<T>::NextNode()
{
    return this->next;
}

//  This methods inserts a node just after the node that the method belongs to 
//  TO-DO: Consider a better implementation
template<class T>
void Node<T>::InsertAfter(Node<T> *p)
{
    // not to lose the rest of the list, we ought to link the rest of the
    // list to the Node<T>* p first
    p->next = this->next;

    // now we should link the previous Node to Node<T> *p , i.e the Node that we are 
    //inserting after,
    this->next = p;
}

// Deletes the node from the list and returns the deleted node
template<class T>
Node<T>* Node<T>::DeleteAfter()
{
    // store the next Node in a temporary Node
    Node<T>* tempNode = next;
    // check if there is a next node
    if(next != NULL)
        next = next->next;

    return tempNode;
}
template<class T>
Node<T> * GetNode(const T& item, Node<T>* nextptr = NULL)
{
    Node<T>* newnode; // Local ptr for new node
    newnode = new Node<T>(item,nextptr);
    if ( newnode == NULL)
    {
        cerr << "Memory allocation failed." << endl;
        exit(1);
    }
    return newnode;
}


      After implementing the node class, now we can implement stacks, queues and the like. Let me implement these structures by using Linked List logic.

      Stack, Queue Properties

      Stack

      If the items are ordered according to the sequence of insertion into the list, this corresponds to a stack.In other words, First In Last Out (FILO) or Last In First Out (LIFO)

      Queue

      A queue is a data structure consisting of a list of items and two pointers to the "front" and "rear" items in the list. Items can only inserted at the rear and removed only at the front. i.e. FIFO (First In First Out) operation.

      I will implement these classes in another article.

      ENJOY!!!!