[Home]  [Edit this page]  [Recent Changes]  [Special Pages]  [Help] 

---

LinkedList

---

(Computer science) Linked List

A linked list is a data structure used to maintain a dynamic series of data. Think of a linked list as a line of elephants in a circus where each elephant is holding on to the tail of the next elephant. If you know where the first elephant is, you can follow it's trunk to the next one. By following trunks, you can find any elephant in the chain. When you get to an elephant that isn't holding on to another elephant's tail, you know you are at the end.

Linked lists work in the same way, except programmers usually refer to nodes instead of elephants. A single node is defined the same way as any other  ?user defined type or object, except that it also contains a pointer to a variable of the same type as itself.

C example node definition

typedef struct lnode
{
    int data;
    struct lnode *next;
} listnode_t;

Once you have a definition for a list node, you can create a list simply by declaring a pointer to the first element, called the "head". A pointer is generally used instead of a regular variable.

C example list definition

listnode_t *head;

It's as simple as that! You now have a linked list data structure. It isn't altogether useful at the moment, but there is something you can do already. You can see if the list is empty:

C linked list example program #1

include <stdio.h>


typedef struct lnode
{
    int data;
    struct lnode *next;
} listnode_t;
int main()
{
    listnode_t *head = NULL; /* initialize list head to NULL */
    if (head == NULL)
    {
        printf("The list is empty!\n");
    }
}

In the next example, you will see new nodes added to the list with the function addNode().

C++ linked list example program #1

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;
    }
    while(curNode->next) curNode=curNode->next;
    curNode->next=new node(data);
}
int main()
{
    addNode(7);
    addNode(1);
    addNode(40);
    node *curNode=head;
    while(node)
    {
        cout << node->data;
        node=node->next;
    }
}

Consider the code fragment:

while(curNode->next) curNode=curNode->next;

This is very common in programs that use linked lists. However, the function could just as easily have been rewritten as:

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

This shows one of the strengths of linked lists. Items can easily be added to the end or beginning (or even the middle) and can be removed just as easily. However, accessing a specific item in the middle is slow compared to array access. It is an O(n) operation, as opposed to an O(1) operation for arrays. (See algorithm for more information on the order of an algorith)

Note that unless you specifically initialize a pointer to some value, it will contain whatever value was in that memory location before. There is no way to know where your pointer might be pointing so it's a good idea to set it to NULL (0, which is not the same as the number 0). NULL pointers will be important as our list grows because a node with a NULL next pointer is the last item in the list (the elephant whose trunk holds no tail).

TODO:

• give example of sorting linked list by swapping pointers
• introduce doubly-linked list and circular list

[Edit this page]  [Page history]  [What links here]  [Discuss this topic]  [Printer Friendly]