Linked List Introduction

1 Types of Data Structures

 Data structures are generally classified into two types:

• Primitive structures: For example integer, real, character, Boolean. These data types are simple as these cannot be further sub-divided.
• Non-primitive structures: For example: Arrays, Trees, Linked List etc. These are complex data types. Based on the arrangement of data, the primitive structures can be further divided into two types: linear and non-linear data structure.
  Linear data structure: In linear data structure, the data is arranged in linear fashion or sequential order. Some of the examples are arrays, linked lists, stacks, queues.
  Non-linear data structure: In non-linear data structure, the data is not arranged in sequence. Some of the examples are trees, graph.

2 Data Structure Operations

            The data stored in data structure is accessed by means of operations. The choice of selecting data structure for particular situation depends upon the frequency operation. Some of the frequently used operations are:

• Insertion: Adding a new record in the data structure.
• Deletion: Remove a record from the data structure.
• Traverse: Accessing each record in the data structure exactly once.
• Search: Searching refers to the process of finding the location of record with given key value or finding the locations of all records which satisfy one or more condition.
• Sorting: Sorting means arranging the records in some pattern.
• Merging: Merging means combining the records of two different sorted files into a single sorted file

1. Linked List

Linked lists are special list of some data elements linked to one another. A single linked list or one way list is a linear collection of data elements, called nodes. Each node has two parts. First part is INFO part which stores the information and another part is POINTER which points to the next elements.

Linked List Example:

Advantages :

1. Linked lists are dynamic data structures , i.e., they can grow or shrink during the execution of a program.

2. Efficient memory utilization. Here, memory is not pre- allocated . Memory is allocated whenever it is required. And deallocated when it is no longer needed.

3. Insertion and deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at specified position and deletion of data item from the given position.

1.9 Terminology

As per the definition linked list is a non sequential collection of data items called nodes. These nodes in principle are structures containing fields. Each node in a linked list has basically two filed.

            1. Data field

            2. Link field

Data field: It contain an actual value to be store and processed.

Link field : The link field contains the address of the next data item in the linked list. The address used to access a particular node is known as a pointer.

Null Pointer: The link field of the last node contains the NULL rather than a valid address. It indicate the end of the list.

External Pointer: It is a pointer to very first node in the linked list. It enable us to access entire node in the linked list.

1.10 Representation:

            A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.
            In C, we can represent a node using structures. Below is an example of a linked list node with integer data.

struct Node

{

    int data;

    struct Node* next;

};

Example Program :

#include <stdio.h>

#include <stdlib.h>

struct Node {

            int data;

            struct Node* next;

};

typedef struct Node NODE

int main()

{

            NODE * head = NULL;

            NODE * second = NULL;

            NODE * third = NULL;

            // allocate 3 nodes  

            head = (NODE*)malloc(sizeof(NODE));                                

            second = (NODE*)malloc(sizeof(NODE));                                  

            third = (NODE*)malloc(sizeof(NODE));                                        

            head->data = 1; // assign data in first node

            head->next = second; // Link first node with

            // the second node

            second->data = 2;

            second->next = third;

            third->data = 3; // assign data to third node

            third->next = NULL;

            return 0;

}

Note that only head is sufficient to represent the whole list.  We can traverse the complete  list by following next pointers

 

3. Operations on Linked List

The following are the basic operations to be performed on linked list

Ø  Creation

Ø  Insertion

Ø  Deletion

Ø  Traversing

Ø  Searching

Ø  Concatenation

Creation: This operation is used to create linked list . Here the constituent node is cfeated as and when it is require and linked to the list.

Insertion: This operation is used to insert the new node in the linked list at specified position. A new node may be inserted at the beginning of the linked list, or at the end of the linked list, or at the specified position of the linked list. If the linked list is empty the inserted node as the first node of the list.

Deletion: This operation is  used to delete node from the linked list. a node may be deleted from the at the beginning of the linked list, or at the end of the linked list, or at the specified position of the linked list.

Traversing: It is a process of going through all nodes of a linked list from one end to another end. if we start traversing from first node towards the last node  it is called forward traversing.

Searching: it is process of finding the item or element in the linked list.

Concatenation: It is a process of appending the second list at the end of the first list.

1.12 Types of linked list

Linked list are represent in four basic types, they are as follows

Ø  Singly-linked list

Ø  Doubly linked list

Ø  Circular linked list

Ø  Circular doubly linked list

4 A single linked list or one way list is a linear collection of data elements, called nodes. Each node has two parts. First part is INFO part which stores the information and another part is POINTER which points to the next elements. The drawback  of the single linked list is that it cannot access the predecessor of the node from the current node. This can ovrcome in doubly linked list.

4.1 Inserting nodes  To insert nodes into inked list , insert an element into the following three things should be done

            A. Allocating node                 B. Assigning the data             C. Adjusting the pointers

            To insert the new node into the linked list has the following three instances

1. A new node may be inserted at the beginning of the linked list.

2. Insert node at the end of the linked list

3. insert node at specified position of the linked list.

A linked list is a data structure which can change during execution.

Successive elements are connected by pointers. in a linked list last element points to NULL.

--> It can grow or shrink in size during execution of a program.

--> It can be made just as long as required.

--> It does not waste memory space.