Linked list

From ArticleWorld

The linked list is one of the fundamental computer science and computer programming data structures. It is made of a series of nodes, containing an arbitrary number of data fields, and at least one reference that points to the next or previous node.

Almost any language supports the implementation of lists. Many of them have the list structures built-in, and some of them, like LISP, actually have the list as their basic data type.

Usage

The linked lists are quite similar to arrays, in the way that they are indexed collections. However, they allow an arbitrary number of points to be inserted at a certain (constant) point. On the other hand, searching and indexing are more time-consuming.

They are the building blocks of some other special data types, like stacks and queues. They are also used to implement association lists, but most programmers prefer to use self-balancing binary search trees for such structures.

They should generally be used when objects are inserted, deleted or moved very frequently, at an arbitrary point in the list, or when the data structure must be persistent. There are some cases when they shouldn't be used. For example, any kind of data that would require random access (i.e. any element in the structure can be accessed in the same amount of time) should be stored in an array.

Programmers of embedded systems usually take some shortcuts when using linked lists, because they require more storage space.

Linked list types

There are several types of linked lists. These are:

1. Linearly-linked lists, which is the simplest kind of linked list. Linearly linked lists can be:

• Singly-linked list, where every node retains a reference to the next object. The reference of the last node is null.
• Doubly-linked lists, which are quite similar to singly-linked list, but each node has two references: one to the previous node, and one to the next. The first node's reference to the precedent node and the last node's reference to the following node are null.

1. Circularly-linked lists, where the first and the last nodes are linked together. Compared to linearly-linked lists, the advantage is that you do not need to "move back" when walking through the list: starting from a node, you will surely come back to it by simply walking forward through the list. These are also singly-linked and doubly-linked, in a manner similar to the linearly-linked lists.

Example

The following is a simple, singly-linked linear list implementation in C:

#include <iostream>
using namespace std;

struct node {
    node(int data_p) { data=data_p; next=0; }
    int data;
    node *next;
};

node *head=0;

void addNode(int data) { 
node *curNode=head;
    if(head==0) {
        head=new node(data);
        return;
    }
    curNode=new node(data);
    curNode->next=head;
    head=curNode;
}

int main() {
    addNode(3);
    addNode(6);
    addNode(11);
    node *curNode=head;
    while(node)
    {
        cout << node->data;
        node=node->next;
    }
}