List In C++

Introduction

 

One way in which more than one object of the same data type can be stored in the memory is by using arrays. Arrays suffer from certain limitations, like fixed size, insertion and deletion of data which involves re-shuffling of array elements. Manipulation is time-consuming and inefficient.

 

Linked list can be used to overcome the limitations imposed by arrays.

 

A linked list is a chain of objects in which each object consists of the data and a pointer that stores the address of the next logical object in the list.

 

Advantage

 

Memory is allocated whenever required. It is not necessary to know the number of elements in advance and allocate memory for linked lists.

 

Inserting to and deleting from linked lists can be handled efficiently without having to restructure the list.

 

Types

 

Linked lists are data structures, which can dynamically change their size. Memory is allocated at run time depending on user requirements.

• Single Linked List
• Circular Linked List
• Double Linked List

Single Linked List

Single Linked List is a chain of structures in which each structure consists of data as well as a pointer. The Pointer stores the address of the next logical structure in the list. Each structure or element of a linked is called a node. Unlike arrays, data in a linked list is not stored in contiguous memory locations but is scattered in different locations. The data is linked together because each node contains the address of the next.

 

Circular Linked List

 

A Circular linked list has the start pointer pointing to the first node and the last pointer instead of containing value NULL, pointing to the first node.

 

Double Linked List

 

A double linked list is also called a two-way list. The node of a double linked list contains:

 

A start pointer, which points to the first node in the list.

 

A last pointer, which points to the last node in the list.

 

Representing the info in a node

 

The class info contains the data stored in a linked list. The data can be a user-defined class or any system defined data-types. It may require storing basic information like name, address, phone number.

 

A node in a list can be defined as, 

class Node {
    string name;
    public: Node * Next;
    Node(const string & nm, Node * n = null)
   }
 }
};

Representing the List Class

 

A linked list is identified by a collection of nodes and a pointer called START that has the address of the first node of the list. 

class List {
    private: node * START;
    public: List() {
        //Initialize all member pointers to null
    }
    void addNote(const string & nm);
    bool delNode(const string & nm);
    bool queryNode(const string & nm);
    void traverse();
};

Insertion of nodes in a linked list

 

Insertion involves adding a new node to an existing linked list or creating a new linked list if one does not already exist. Insertion can be performed at the beginning of the list, in the middle of the list, or at the end of the list. The function addnote() manages the insertion of the node in the list. It takes the string as a parameter.

void List: : add_Node(const string & nm) {
    if (START == NULL || nm <= START - > INFO) {
        START = new Node(nm, START);
        return;
    }
}

Traversing a linked list

 

To display the contents of a list, it needs to traverse the list. Set a temporary pointer temp to START. Display the INFO part of the node. Advance the pointer temp so that it points the next node. Repeat the step 2 and 3 untill temp is not equal to NULL. 

void List: : traverse() {
    for (Node * temp = START; temp != NULL; temp = temp - > NEXT) {
        cout << temp - > name << endl;
    }
}

Deleting nodes

 

Logical deletion of the node from the linked list consists of de-linking the node from the list.

 

Physical deletion of the node to free the memory occupied by the node. The delete operator can be used to free the memory occupied by the node.