A linked list consists of a sequence of objects known as nodes.

Each node contains

• arbitrary data fields;

• link pointing to the next node;

• (optional) link pointing to the previous node.

For example, a singly-linked list contains two values:

• the value of the current node

• link to the next node:

  
  struct Node
  {
      int data;
      Node* pnext;
  };
  
  

C-style design model is using global functions and structs to hold data:

//Node.h
struct Node {
    int data;
    Node* next;
};
void insert_front(
    struct Node* node,
    struct Node* newNode )
{
    newNode->next = node->next;
    node->next = newNode;
}

#include <cstddef>
#include "Node.h"
int main ( )
{
    struct Node A;
    struct Node B;
    struct Node C;

    A.data = 12;
    B.data = 99;
    C.data = 37;

    insert_front( &A, &C );
    insert_front( &A, &B );
    C.next = NULL;

    return 0;
}

A typical C++ class has private member variables and public member functions to access and modify data.

This is appropriate design model for a linked list constructed from node objects with basic techniques for:

• data read/write access

• building and maintaining linkage between nodes to form a list.

As before, the linked list is constructed using pointers:

class Node {
    Node* pnext;
public:
    int data;

    // Constructor taking initial value:
    Node( int value = 0 );

    // Insert node in front:
    void insert( Node* newNode );

    // Remove node in front:
    void remove_next();

    // Calculate number of nodes in the list:
    size_t size() const;

    // Calculate distance to other node:
    int distance( Node const* other ) const;
};

Each node keeps user data and a pointer to the next node in the list.

It is a good idea to initialize the pointer with NULL, indicating that no further linkage is present.

NULL becomes the end marker of the singly-linked list.

The definition of NULL comes from a number of the standard library headers, such as <iostream> and <cstddef>.

NULL can be assigned to a pointer of any type.

class Node {
    Node* pnext;
public:
    int data;

    // Constructor taking initial value:
    Node( int value = 0 )
    : pnext( NULL ), data( value )
    {
    }
};

// Node.h
class Node {
    Node* pnext;
public:
    int data;

    // Insert new node in front:
    void insert( Node* newNode )
    {
        newNode->pnext = pnext;
        pnext = newNode;
    }
};

The following diagram shows how it works:

To insert a new node into the list, program must keep track of the previous node.

Inserting a node before an existing one cannot be done.

#include "Node.h"
int main ( )
{
    Node A;
    Node B;
    Node C;

    A.data = 12;
    B.data = 99;
    C.data = 37;

    A.insert( &C );
    A.insert( &B );

    return 0;
}

// Node.h
class Node {
    Node* pnext;
public:
    int data;

    // Remove node in front:
    void remove_next()
    {
        if ( pnext == NULL ) return;
        Node* obsolete = pnext;
        this->pnext = obsolete->pnext;
        // Make node "single":
        obsolete->pnext = NULL;
    }
};

The following diagram shows how it works:

To remove the node, program must again keep track of the previous node:

#include "Node.h"
int main ( )
{
    Node A;
    Node B;
    Node C;
    A.data = 12;
    B.data = 99;
    C.data = 37;
    A.insert( &C );
    A.insert( &B );

    A.remove_next();

    return 0;
}

List traversal employs a linear search algorithm:

// Node.h
class Node {
    Node* pnext;
public:
    int data;
    // Measure distance to other node:
    int distance( Node const* other ) const
    {
        int hops = 1;
        Node const* iter = pnext;
        while ( iter != other ) {
            if ( iter == NULL )
                return hops - 1;
            iter = iter->pnext;
            ++hops;
        }
        return hops;
    }
    // Calculate number of nodes in the list:
    size_t size() const
    {
        return distance( NULL );
    }
};

#include <iostream>
#include "Node.h"
using namespace std;
int main ( )
{
    Node A;
    Node B;
    Node C;
    A.data = 12;
    B.data = 99;
    C.data = 37;
    A.insert( &C );
    A.insert( &B );
    cout << "List size is: " << A.size();
    return 0;
}

The list is searched until the node in question is found.

The distance is measured by the number of hops required.

Again, list traversal by linear search algorithm:

#include <iostream>
using namespace std;
// Node.h
class Node {
    friend void print_list( Node const& head );
    Node* pnext;
public:
    int data;
    // ...
};

// Print contents of the list:
void print_list( Node const& head )
{
    cout << '[' << head.size() << "] ";
    Node const* iter = &head;
    do {
        cout << iter->data << ' ';
        iter = iter->pnext;

    } while ( iter != NULL );
    cout << '\n';
}

#include "Node.h"
int main ( )
{
    Node A;
    Node B;
    Node C;

    A.data = 12;
    B.data = 99;
    C.data = 37;

    A.insert( &C );
    A.insert( &B );

    print_list( A );

    return 0;
}
/* Program output:
[3] 12 99 37
*/

The STL list class provides:

• functions for insertion and removal of elements

• facilities for iteration over the elements in forward and reverse order

Node manipulation is hidden from the user.

#include <iostream>
#include <list>
using namespace std;
int main ()
{
     // Two ints with a value of 100:
    list< int > mylist( 2, 100 );
    mylist.push_front( 200 );
    mylist.push_front( 300 );
    mylist.push_back( 555 );

    cout << "mylist contains:";
    list<int>::iterator it;
    for ( it = mylist.begin(); it != mylist.end(); ++it )
    {
        cout << " " << *it;
    }
    cout << endl;
    return 0;
}
/* Program output:
mylist contains: 300 200 100 100 555
*/

tree