Understanding Data Structures - Linked Lists

A linked list is the most commonly used data structure and the base of other complicated data structures. Linked list is used to store data at runtime or dynamically while program is running.

We all know what linked list is, it is a series of nodes which contains a data and pointer pointing to other nodes. A linked list is accessed by using a pointer or object that points to the head or first node of the linked list.

There are many types of linked lists such as Singly Linked Lists, Doubly Linked Lists, Multiple Linked Lists, Circular Linked Lists, Generic Linked Lists etc. We will implement a linked list in structure oriented languages like C and also in object-oriented languages like C++,C#,Java,Python,VB.Net.

We will also use linked list to implement a simple Student Information System to store data in C#.

 

Let's see some uses of linked lists. 

• File Systems
• Memory manager
• Reading/Writing data from/to peripheral devices such as Computer Screen, Printer, USB Flash drive etc.
• UI operations like next or previous on applications like Video/Music player, Browser etc.
• Sending/Receiving packet data over network or also in telecommunication system.
• Enterprise Application Software(EAS)
• To implement Stack,Queue,Hash Tables etc., Stack for Undo and Queue for Redo operations etc.
• Compilers and Interpreters

There are some drawbacks of linked lists, such as random-access, searching, extra memory etc.

All right, let's go through Singly Linked Lists and Doubly Linked Lists. To verify the linked list we will also print the memory location of each node as well as next/prev node. See the thisNode number and validate it that linked list is formed correctly or not.

Singly Linked Lists

A singly linked list contains a data section and a pointer to next node. Data section may contain any kind of data or pointer or class objects. Next section contains the address of the next node or reference of the next node object.

See following image.

This image shows the singly linked list but not how to implement it. This is just the basic image over the internet for linked list. it doesn't describe much of the singly linked list. See the following modified image to understand it.

 

 

Each node is the record that stores some data. A record can be any type such as structures in C or classes in object-oriented languages. A data can be assigned to the each node of pointer or object.

See the following simple implementation of singly linked list in structure-oriented and in object-oriented.

In C and in C++ you must allocate a memory as well as releasing it once you have done with it. Other object-oriented languages support garbage collection, so no need to worry about memory releasing.

 

Structured Oriented (C)

First you must create an empty project in Visual Studio as Visual C++ and then add new item to it. First let's define the structure to store our data or to build an abstract data type.

typedef struct node {
    int data;
    struct node *next;
}Node;

As shown in the image you can directly assign a same type pointer variable to another pointer variable. In C you have to allocate memory using malloc() function.you can directly allocate memory and assign a data to it or can write a function for it.

Following function assigns data to newnode and next pointer to NULL after allocating memory to it and returns the allocated memory location. You can print a memory location in C using %p format specifier.

Download the source code.

Node *getNewNode(int data)
{
    Node *newnode = (Node*)malloc(sizeof(Node));
    if (newnode != NULL){
        newnode->data = data;
        newnode->next = NULL;
    }
    return newnode;
}

In main function, assign or form the next pointer by assigning other pointer nodes to it as shown in above image. First create a head and set it to NULL.You can directly assign allocated memory node to head by calling getNewNode(). Then create three nodes, assign node_1 to head and form a linked list by assigning pointer nodes to each other. 

You can also write a function for it that can add node to the list. Then we are printing data of each node,you can put it in while loop, as we generally do. Remember we are doing here only pointer assignment and nothing else to form a linked list.

int main()
{
    Node *head = NULL;
    Node *node_1 = getNewNode(10);
    Node *node_2 = getNewNode(20);
    Node *node_3 = getNewNode(30);
    head = node_1;
    node_1->next = node_2;
    node_2->next = node_3;
    node_3->next = NULL;
    printf("node_1 = %d, node_2 = %d, node_3 = %d\n", head->data, head->next->data, head->next->next->data);
    getchar();
    return 0;
}

Object Oriented

In object-oriented, the procedure is same as in structure oriented, only difference is to play with objects. First define the class of a node and then the procedure is the same. In object-oriented, you dont need a function like getNewNode(), you can directly allocate memory using new keyword. 

class Node {
    int data;
    Node next;
    public Node(int data){
        this.data = data;
        this.next = null;
    }
}

class Program{
    static void Main(string[] args){
        Node head = null;
        Node node_1 = new Node(10);
        Node node_2 = new Node(20);
        Node node_3 = new Node(30);
        head = node_1;
        node_1.next = node_2;
        node_2.next = node_3;
        node_3.next = null;
        Console.WriteLine("node_1 = %d, node_2 = %d, node_3 = %d\n", head.data, head.next.data, head.next.next.data);
        Console.Read();
    }
}

Doubly Linked Lists

A doubly linked list contains a data section, a pointer to next node and a pointer to the previous node. Data section may contain any kind of data or pointer or class objects. Next section contains the address of the next node or reference of the next node object. Prev section contains the address of the previous node or reference of the previous node object. 

See following image. 

 

It doesn't describe much of the doubly linked list. See the following modified image to understand it.

 

 

Just add only one field to the singly linked list as before. And change pointer or object location of previous pointers or objects as shown in above image.

typedef struct node {
    int data;
    struct node *next;
    struct node *prev;
}Node;

class Node {
    int data;
    Node next;
    Node prev;
}

Many operations can be applied on linked list according to its uses as described above. We will see only a few operations such as adding node to end or front and deleting front or last node in linked list. We will implement both singly linked list as well as doubly linked list. Let's see the implementation of the linked list in various programming languages.

 

C

Download the source code for C to view the complete code. 

typedef struct sll_node
{
    int data;
    struct sll_node *next;
}SLL_Node;

typedef struct dll_node
{
    int data;
    struct dll_node *next;
    struct dll_node *prev;
}DLL_Node;

SLL_Node *sll_getNewNode(int data)
{
    SLL_Node *newnode = NULL;
    newnode = (SLL_Node*)malloc(sizeof(SLL_Node));
    if (newnode != NULL){
        newnode->data = data;
        newnode->next = NULL;
    }
    return newnode;
}

DLL_Node *dll_getNewNode(int data)
{
    DLL_Node *newnode = NULL;
    newnode = (DLL_Node*)malloc(sizeof(DLL_Node));
    if (newnode != NULL){
        newnode->data = data;
        newnode->next = NULL;
        newnode->prev = NULL;
    }
    return newnode;
}

typedef struct singly_linked_list{

    SLL_Node *head;
    SLL_Node*(*getNewNode)(int);
    void(*addNodeToEnd)(SLL_Node**, int);
    void(*addNodeToFront)(SLL_Node**, int);
    void(*deleteLastNode)(SLL_Node**);
    void(*deleteFrontNode)(SLL_Node**);
    void(*display)(SLL_Node*);

}SinglyLinkedList;

typedef struct doubly_linked_list{

    DLL_Node *head;
    DLL_Node*(*getNewNode)(int);
    void(*addNodeToEnd)(DLL_Node**, int);
    void(*addNodeToFront)(DLL_Node**, int);
    void(*deleteLastNode)(DLL_Node**);
    void(*deleteFrontNode)(DLL_Node**);
    void(*display)(DLL_Node*);

}DoublyLinkedList;

SinglyLinkedList *initSinglyLinkedList()
{
    SinglyLinkedList *s_list = (SinglyLinkedList*)malloc(sizeof(SinglyLinkedList));
    s_list->head = NULL;
    s_list->getNewNode = sll_getNewNode;
    s_list->addNodeToEnd = sll_addNodeToEnd;
    s_list->addNodeToFront = sll_addNodeToFront;
    s_list->deleteLastNode = sll_deleteLastNode;
    s_list->deleteFrontNode = sll_deleteFrontNode;
    s_list->display = sll_display;
    return s_list;
}

DoublyLinkedList *initDoublyLinkedList()
{
    DoublyLinkedList *d_list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
    d_list->head = NULL;
    d_list->getNewNode = dll_getNewNode;
    d_list->addNodeToEnd = dll_addNodeToEnd;
    d_list->addNodeToFront = dll_addNodeToFront;
    d_list->deleteLastNode = dll_deleteLastNode;
    d_list->deleteFrontNode = dll_deleteFrontNode;
    d_list->display = dll_display;
    return d_list;
}

There is no class in C, but we can implement class in C using pointer to functions and putting it in a structure. The structure singly_linked_list defines all the pointer to function methods. initSinglyLinkedList() and initDoublyLinkedList() initialize the pointer to function by assigning functions to it. And then we can access all functions from the variable of structure SinglyLinkedList or DoublyLinkedList.

C++

Download the source code for C++ to view complete code. 

class SLL_Node{
public :
    int data;
    SLL_Node *next;
    SLL_Node(int data){
        this->data = data;
        this->next = nullptr;
    }
};

class DLL_Node{
public:
    int data;
    DLL_Node *next;
    DLL_Node *prev;
    DLL_Node(int data){
        this->data = data;
        this->next = nullptr;
        this->prev = nullptr;
    }
};

class SinglyLinkedList{
private:
    SLL_Node *head = nullptr;
    SLL_Node *lastNode = nullptr;
    int count = 0;
public:
    void addNodeToEnd(int);
    void addNodeToFront(int);
    void deleteLastNode();
    void deleteFrontNode();
    int getCount();
    void display();
};

class DoublyLinkedList{
private:
    DLL_Node *head = nullptr;
    DLL_Node *lastNode = nullptr;
    int count = 0;
public:
    void addNodeToEnd(int);
    void addNodeToFront(int);
    void deleteLastNode();
    void deleteFrontNode();
    int getCount();
    void display();
};

C#

Download the source code for C# to view complete code. C# stores objects in hash tables, so you can print the hash code of the stored object for printing memory location. 

See following display() function. 

class SLL_Node
{
    public int data;
    public SLL_Node next;
    public SLL_Node(int data){
        this.data = data;
        this.next = null;
    }
}

class DLL_Node
{
    public int data;
    public DLL_Node next;
    public DLL_Node prev;
    public DLL_Node(int data){
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class SinglyLinkedList
{
    private SLL_Node head = null;
    private SLL_Node lastNode = null;
    private int count = 0;

    ....
}

class DoublyLinkedList
{
    private DLL_Node head = null;
    private DLL_Node lastNode = null;
    private int count = 0;
    ....
}

public void display(){
    SLL_Node current = this.head;
    while(current != null){
        Console.Write("  data = " + current.data + ", thisNode = " + current.GetHashCode());
        if (current.next != null){
            Console.WriteLine(", next = " + current.next.GetHashCode());
        }else{
            Console.WriteLine(", next = null");
        }
        current = current.next;
    }
}

Java

Download the source code for Java to NetBeans to view complete code. The source code for Java is the same as C#. 

class SLL_Node{
    public int data;
    public SLL_Node next;
    public SLL_Node(int data){
        this.data = data;
        this.next = null;
    }
}

class DLL_Node{
    public int data;
    public DLL_Node next;
    public DLL_Node prev;
    public DLL_Node(int data){
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

Python

Download the source code for Python to view complete code. For Python, you need to install Python tools in Visual Studio. 

class SLL_Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class DLL_Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class SinglyLinkedList:
    head = None
    lastNode = None
    count = 0
    ....

class DoublyLinkedList:
    head = None
    lastNode = None
    count = 0
    ....

VB.Net

Download the source code for VB.Net to view complete code. VB.Net stores objects in hash tables, so you can print the hash code of the stored object for printing memory location.

See following display() function. 

Public Class SLL_Node
    Public data As Integer
    Public nextNode As SLL_Node
    Public Sub New(ByVal data_val As Integer)
        MyClass.data = data_val
        MyClass.nextNode = Nothing
    End Sub
End Class


Public Class DLL_Node
    Public data As Integer
    Public nextNode As DLL_Node
    Public prevNode As DLL_Node
    Public Sub New(ByVal data_val As Integer)
        MyClass.data = data_val
        MyClass.nextNode = Nothing
        MyClass.prevNode = Nothing
    End Sub

End Class


Public Class SinglyLinkedList
    Private head As SLL_Node = Nothing
    Private lastNode As SLL_Node = Nothing
    Private count As Integer = 0
    ....


Public Class DoublyLinkedList
    Private head As DLL_Node = Nothing
    Private lastNode As DLL_Node = Nothing
    Private count As Integer = 0
    ....


Public Sub display()
    Dim current As SLL_Node = MyClass.head
    While current IsNot Nothing
        Console.Write("  data = " & current.data & ", thisNode = " & current.GetHashCode())
        current = current.nextNode
        If current Is Nothing Then
            Console.WriteLine(", next = null")
        Else
            Console.WriteLine(", next = " & current.GetHashCode())
        End If
    End While
End Sub

If you compare the source codes in object oriented programming languages. You will find that they all are same but their syntax. To build the generic linked list in C# see following code.

It takes a type T as data with Data & Next properties and the remaining code is same as above C# code.  

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GenericLinkedList
{
    public class Node<T>
    {
        private T data;
        private Node<T> next;
        public Node(T data)
        {
            this.data = data;
            this.next = null;
        }

        public T Data
        {
            get { return this.data; }
            set { this.data = value; }
        }

        public Node<T> Next
        {
            get { return this.next; }
            set { this.next = value; }
        }
    }

    class LinkedList<T>
    {
        private Node<T> head;
        private Node<T> lastNode;
        private int count = 0;

        public Node<T> Head { get { return this.head; } }

        public Node<T> LastNode
        {
            get { return lastNode; }
            set { this.lastNode = value; }
        }

        public void addNodeToEnd(T data)
        {
            Node<T> current = this.head;
            if (current == null)
            {
                this.head = new Node<T>(data);
                this.lastNode = this.head;
                this.count++;
            }
            else
            {
                if (this.lastNode != null)
                {
                    this.LastNode.Next = new Node<T>(data);
                    this.lastNode = this.lastNode.Next;
                    this.count++;
                }
            }
        }

        public int getCount()
        {
            return this.count;
        }

        public void display()
        {
            Node<T> current = this.head;
            while (current != null)
            {
                Console.Write(current.Data+" ");
                current = current.Next;
            }
            Console.WriteLine();
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            //linked list of int
            LinkedList<int> list = new LinkedList<int>();
            list.addNodeToEnd(10);
            list.addNodeToEnd(20);
            list.addNodeToEnd(30);
            list.display();
            //linked list of string
            LinkedList<String> strlist = new LinkedList<String>();
            strlist.addNodeToEnd("hello");
            strlist.addNodeToEnd("world");
            strlist.addNodeToEnd("!!!");
            strlist.display();
            //linked list of linked list of string
            LinkedList<LinkedList<String>> strListOfList = new LinkedList<LinkedList<String>>();
            strListOfList.addNodeToEnd(strlist);
            strListOfList.display();
            Console.Read();
        }
    }
}