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 - Cheap photo paper at Sunday, March 3, 2013 3:09 AM

Fantastic blog article.Really looking forward to read more. Really Great.

Posted by anonymous - A4 photo paper at Sunday, March 3, 2013 4:00 AM

I value the article post.Thanks Again. Want more.

Posted by anonymous - Cheap a4 photo paper at Sunday, March 3, 2013 4:52 AM

I really liked your post.Really thank you!

Posted by anonymous - Inkjet photo paper at Sunday, March 3, 2013 5:47 AM

Wow, great article post. Great.

Posted by anonymous - Works at Wednesday, October 23, 2013 7:54 PM

It works nice very nice

What is running time?

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.