Friday, July 25, 2008

What is a singly linked list? How to implement singly linked lists in C++?

This article explains the concept of singly linked list data structure and provides a sample implementation in C++.
  • Linked lists are building blocks for many other data structures like stacks and queues.
  • Linked lists are a sequence of nodes containing data fields and pointers to the next node (or) next node and previous nodes based on its type.
  • Linked lists permit addition/ removal of node in constant time.
  • Unlike arrays the order of linked list elements need not be contiguous in memory.
  • Unlike arrays there is no upper limit on the amount of memory reserved.
  • A singly linked list is the simplest of linked lists.
  • Each node of a singly linked list has data elements and a single link (pointer) that points to the next node of the list (or) NULL if it is the last node of the list.
  • Addition/ Deletion of a node to the singly linked list involves the creation/ deletion of the node and adjusting the node pointers accordingly.
  • A singly linked list could be represented as below:-

Demonstrate the implementation of a singly linked list

#include <iostream>
using namespace std;

// Node class
class Node {
    int data;
    Node* next;

  public:
    Node() {};
    void SetData(int aData) { data = aData; };
    void SetNext(Node* aNext) { next = aNext; };
    int Data() { return data; };
    Node* Next() { return next; };
};

// List class
class List {
    Node *head;
  public:
    List() { head = NULL; };
    void Print();
    void Append(int data);
    void Delete(int data);
};

/**
 * Print the contents of the list
 */
void List::Print() {

    // Temp pointer
    Node *tmp = head;

    // No nodes
    if ( tmp == NULL ) {
    cout << "EMPTY" << endl;
    return;
    }

    // One node in the list
    if ( tmp->Next() == NULL ) {
    cout << tmp->Data();
    cout << " --> ";
    cout << "NULL" << endl;
    }
    else {
    // Parse and print the list
    do {
        cout << tmp->Data();
        cout << " --> ";
        tmp = tmp->Next();
    }
    while ( tmp != NULL );

    cout << "NULL" << endl;
    }
}

/**
 * Append a node to the linked list
 */
void List::Append(int data) {

    // Create a new node
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->SetNext(NULL);

    // Create a temp pointer
    Node *tmp = head;

    if ( tmp != NULL ) {
    // Nodes already present in the list
    // Parse to end of list
    while ( tmp->Next() != NULL ) {
        tmp = tmp->Next();
    }

    // Point the last node to the new node
    tmp->SetNext(newNode);
    }
    else {
    // First node in the list
    head = newNode;
    }
}

/**
 * Delete a node from the list
 */
void List::Delete(int data) {

    // Create a temp pointer
    Node *tmp = head;

    // No nodes
    if ( tmp == NULL )
    return;

    // Last node of the list
    if ( tmp->Next() == NULL ) {
    delete tmp;
    head = NULL;
    }
    else {
    // Parse thru the nodes
    Node *prev;
    do {
        if ( tmp->Data() == data ) break;
        prev = tmp;
        tmp = tmp->Next();
    } while ( tmp != NULL );

    // Adjust the pointers
    prev->SetNext(tmp->Next());

    // Delete the current node
    delete tmp;
    }
}

int main()
{
    // New list
    List list;

    // Append nodes to the list
    list.Append(100);
    list.Print();
    list.Append(200);
    list.Print();
    list.Append(300);
    list.Print();
    list.Append(400);
    list.Print();
    list.Append(500);
    list.Print();

    // Delete nodes from the list
    list.Delete(400);
    list.Print();
    list.Delete(300);
    list.Print();
    list.Delete(200);
    list.Print();
    list.Delete(500);
    list.Print();
    list.Delete(100);
    list.Print();
}

OUTPUT:-
100 --> NULL
100 --> 200 --> NULL
100 --> 200 --> 300 --> NULL
100 --> 200 --> 300 --> 400 --> NULL
100 --> 200 --> 300 --> 400 --> 500 --> NULL
100 --> 200 --> 300 --> 500 --> NULL
100 --> 200 --> 500 --> NULL
100 --> 500 --> NULL
100 --> NULL
EMPTY

39 comments :

  1. I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.

    Kaylee

    http://www.thinkpadonline.info

    ReplyDelete
  2. I recently came accross your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.


    Joyce

    http://www.shunmigraine.com

    ReplyDelete
  3. It seems to me that your site has a lot of interesting and informative articles. Surely, I will introduce it to my friends. Keep it up!

    Realities and Realizations
    Innovations and Services

    ReplyDelete
  4. Nice writing... I'll be back to check for more!

    ReplyDelete
  5. I need the following C++ Programs.. Kindly send me. my id is jeganme.s1@gmail.com

    1. Design C++ classes with static members, methods with default arguments, friend functions. (For example, design matrix and vector classes with static allocation, and a friend function to do matrix-vector multiplication)
    2. Implement complex number class with necessary operator overloadings and type conversions such as integer to complex, double to complex, complex to double etc.
    3. Implement Matrix class with dynamic memory allocation and necessary methods. Give proper constructor, destructor, copy constructor, and overloading of assignment operator.
    4. Overload the new and delete operators to provide custom dynamic allocation of memory.
    5. Develop a template of linked-list class and its methods.
    6. Develop templates of standard sorting algorithms such as bubble sort, insertion sort, merge sort, and quick sort.
    7. Design stack and queue classes with necessary exception handling.
    8. Define Point class and an Arc class. Define a Graph class which represents graph as a collection of Point objects and Arc objects. Write a method to find a minimum cost spanning tree in a graph.
    9. Develop with suitable hierarchy, classes for Point, Shape, Rectangle, Square, Circle, Ellipse, Triangle, Polygon, etc. Design a simple test application to demonstrate dynamic polymorphism and RTTI.
    10. Write a C++ program that randomly generates complex numbers (use previously designed Complex class) and writes them two per line in a file along with an operator (+, -, *, or /). The numbers are written to file in the format (a + ib). Write another program to read one line at a time from this file, perform the corresponding operation on the two complex numbers read, and write the result to another file (one per line).

    ReplyDelete
  6. Your post really helped me, but i have a request: it would be great if you'll have an article about double linked list in c++ using classes and how to implement it.

    ReplyDelete
  7. This comment has been removed by a blog administrator.

    ReplyDelete
  8. Very useful site. Good tutorials on C++.
    Thanks.

    ReplyDelete
  9. Good post. I just came and wanted to say that I really enjoyed viewing your blog. In any case college board will be useful.

    ReplyDelete
  10. One thing to note about the List::Delete function:
    It does not check if the data actually exists before something is deleted in the case "Last node of the list".
    This is easy to modify however. Really nice job on this class, its very clean and easy to understand.

    ReplyDelete
  11. dear JEGAN.S, what a douchebag!

    ReplyDelete
  12. small glitch, otherwise appreciable ..

    in delete if we give non existent data, after while ends the setNext delete , dumps !!

    think,
    Node *prev;
    do {
    if ( tmp->Data() == data )
    {
    /*Needed Fix as below*/
    // Adjust the pointers
    prev->SetNext(tmp->Next());

    // Delete the current node
    delete tmp;
    break;
    }
    prev = tmp;
    tmp = tmp->Next();
    } while ( tmp != NULL );

    }

    ReplyDelete
  13. it helps me a lot. . .thanx for that.. now my doubts are all clear.. :)

    ReplyDelete
  14. it's awesome!!!!!!!!!!!!!!!1

    ReplyDelete
  15. Thanks!! It got me pass the hurdle.

    ReplyDelete
  16. Great blog! Thanks a lot!

    I run some tests and add some code to List::Delete() to delete "head" Node properly and not delete tmp if tmp is NULL -- means no matched Node found:
    /**
    * Delete a node from the list
    */
    void List::Delete(int data) {

    // Create a temp pointer
    Node *tmp = head;

    // No nodes
    if ( tmp == NULL )
    return;

    // Last node of the list
    if ( tmp->Next() == NULL ) {
    delete tmp;
    head = NULL;
    }
    else {
    // Parse thru the nodes
    Node *prev = NULL;
    do {
    if ( tmp->Data() == data ) break;
    prev = tmp;
    tmp = tmp->Next();
    } while ( tmp != NULL );

    // Adjust the pointers
    if ( prev != NULL && tmp != NULL )
    prev->SetNext(tmp->Next());

    // Adjust head to next if needed
    if ( head == tmp )
    head = tmp->Next();

    // Delete the current node if we found
    if ( tmp != NULL )
    delete tmp;

    }
    }

    ReplyDelete
  17. Hi your blog is too good. It helps me to study singly linked list using class.

    ReplyDelete
  18. Your blog is really helpful....Keep it up and Thanx

    ReplyDelete
  19. Thank's Dude it really works.

    ReplyDelete
  20. thanks a lot,each and every thing so nice and simple

    ReplyDelete
  21. i am currently student of computer science written a code in c++ for the implementation of link list.this is link to it
    http://softwares-mart.blogspot.com/2012/12/c-source-code-for-link-list-free.html

    ReplyDelete
  22. Thanks! found C code using structs etc... nice to just get C++ where the code makes sense and I don't have to read 30 pages of who what not because the code was a lil messy...

    ReplyDelete
  23. Why to use classes for linked list when samething can be done using structs?

    ReplyDelete
  24. If we delete the very first node in the first attempt to delete any node from the linked list then the above program get crashed.Why?

    ReplyDelete
  25. What is the license for using code from this site?
    Please let it be MIT or BSD license...
    Thanks,
    Pat

    ReplyDelete
  26. If we do a little modification in the Delete function as below then it not going to assert even if we delete the very first node of the linked list in the first attempt.The code :
    void List::Delete(int aData)
    {
    Node *temp = head;
    Node *prev;
    if (temp == NULL)
    {
    cout << "List is empty";
    return;
    }
    //only one node
    if (temp->Next() == NULL)
    {
    head = NULL;
    delete temp;
    }
    else
    {
    while(temp->Next() != NULL)
    {
    if (temp->Data() == aData)
    {
    if (head == temp)
    {
    head = head->Next();
    delete temp;
    return;
    }
    break;
    }
    prev = temp;
    temp = temp->Next();
    }
    prev->SetNext(temp->Next());
    delete temp;
    }
    }

    Thanks to everyone those who go through my code.
    Thanks and Regards;
    Brijendra Sharma

    ReplyDelete
  27. I need the c++ program for the following.Kindly send it to nikhilaachuthan@ymail.com
    1.Develop a template of linked-list class and its methods.
    2.Design stack and queue classes with necessary exception handling.

    ReplyDelete
  28. How can i add a data at the end of the list ? plz help me

    ReplyDelete
  29. Thankyou so much for sharing this!
    after read this article, i get better understanding linked list and the implementation.
    God bless your hard work!

    ReplyDelete
  30. Why do we need two use two classes?
    why can't the same be done using only one class?

    ReplyDelete
  31. helped a lot....
    but can't understand how to insert an element between two elements in the list?

    ReplyDelete


  32. Very informative article.Thank you author for posting this kind of article .



    http://www.wikitechy.com/view-article/explain-in-details-about-array-implementation-of-linked-list-in-c



    Both are really good,.
    Cheers,
    Venkat

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top