Article 83 - Data Structure - How to Implement Linked List in C

This article describes an implementation of the Linked List Structure.

For information about the Linked List Structure, see Article 31 - Programming Data Structures.

To program a Linked List, we need to understand the interface of a Linked List.

Interface

  • Add Node
  • Remove Node
  • Find Node

Implementation

The structure of a node in the linked list.

typedef struct Node{
    struct Node * next;
    int content;
} Node;

New Node Function

Node * newNode( int content ){
    Node * newNode = (Node *)malloc( sizeof(Node) );
    
    if( !newNode ){
        return 0;
    }

    newNode->next = 0;
    newNode->content = content;

    return newNode;
}

Add Node Function

There are two options, prepend at beginning, or append at end of list. In this article, we append to the beginning for simplisticity.

Appending a node at the end is simply an application of iterating through the list. We encourage the the reader implement this for practice.

A function to add a node to the linked list and update the head pointer.

int addNode( Node ** head, Node * node ){
    if( !head ){
        return -1;
    }

    if( !node ){
        return 0;
    }

    node->next = *head;
    *head = node;

    return 0;
}

Remove Node Function

To remove a node, iterate through the list to find the particular node and remove it from the list.

Care must be taken when removing the head node, as the function must update the head pointer.

A function to remove a node from the linked list and update the head pointer if necessary.

int removeNode( Node ** head, Node * node ){
    Node * previousNode;
    Node * currentNode;

    if( !head ){
        return -1;
    }

    previousNode = *head;

    if( !previousNode ){
        return 0;
    }

    if( previousNode == node ){
        *head = previousNode->next;
        free( previousNode );
        return 0;
    }

    for( currentNode = previousNode->next; !currentNode; 
        previousNode = previousNode->next, 
        currentNode = currentNode->next ){   
        if( currentNode == node ){
            previousNode->next = currentNode->next;
            free( currentNode );

            break;
        }
    }

    return 0;
}

Find Node Function

To search for a node is simply an application of the Remove Node Function. In fact, it is often easier to write the Find Node Function first and clone it for removing a node. Instead of removing a node, the Find Node Function returns the content found, or some error if the node does not exist.

Comments (19)

Posted by anonymous - Programmer at Friday, December 7, 2012 9:52 PM

Nice~

Posted by anonymous - Nv at Friday, December 21, 2012 11:54 AM

This works.

Posted by anonymous - custom at Wednesday, January 2, 2013 11:30 PM

Hotsays it works well

Posted by anonymous - ??? at Friday, February 1, 2013 10:22 AM

find miumiu,chloe,prada in the fashion style and low price. More other products can be found here in website. ??? http://www.prada-rakuten.jp/

Posted by anonymous - ??? ?? at Sunday, February 3, 2013 2:20 AM

find miumiu,chloe,prada is too many type and you may have no idea about such many type. ??? ?? http://www.chloe-mall.net/

Posted by anonymous - social bookmarks at Saturday, March 2, 2013 5:35 AM

KmykfJ I am so grateful for your blog. Really Great.

Posted by anonymous - viagra discount at Saturday, March 2, 2013 1:17 PM

Awesome article.Really thank you! Really Cool.

Posted by anonymous - buy viagra online at Saturday, March 2, 2013 1:18 PM

Appreciate you sharing, great blog post.Much thanks again. Will read on...

Posted by anonymous - Samsung 4072 4pack at Saturday, March 2, 2013 3:21 PM

A round of applause for your article post.Really thank you! Awesome.

Posted by anonymous - samsung k4072 at Saturday, March 2, 2013 4:12 PM

I really enjoy the blog article. Cool.

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.