Memory Allocation/Linked List Method’s Link

      

Introduction

  • Linked list is also known as ‘Self Referential Structure‘, because a member of the structure/node is declared as a pointer that points to same (but another) structure/node in the list.
  • Structure is the most appropriate data structure to represent linked list.
  • Like arrays, Linked list is also a primitive data structure.
  • Linked list overcomes the disadvantages of array by providing flexibility in the program.
  • Linked list is the second most-used data structure after array.  
  • A linked list is useful specially when –
    • The amount of data to be stored can’t be predicted in advance since it is a dynamic data type.
    • Data will frequently be inserted or deleted.
  • It is a dynamic data structure.

Definition

  • A linked list is a collection of records of the same data type and all the records are connected through pointers.
  • A linked list is a non-sequential collection of data items.
  • A linked list is a sequence of linked data items, which are connected together via links.

Features

  • Like arrays, linked list also has an easy/efficient sequential access.
  • Linked lists allocate memory for each element separately and only when necessary.
  • Unlike an array, in linked list insertion, deletion, rearrangement of data items etc. operations  are easy and occurs at any position in the list because they need a few computations at run time by allocating additional memory space or to release unwanted space. Thus, it optimizing the use of storage space.
  • A node of a linked list consists of two parts – Data part and Address part.Data part stores the user’s data and address part contains the address of next connected node and so on. The address part of last node of a linked list contains NULL. 
  • For every data item in a linked list, there is an associated pointer that would give the memory location of the next data item in the linked list.
  • The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item.
  • In linked list, size declaration is optional i.e.,it may be more or less than the equal size.
  • Memory allocation occurs dynamically i.e., a linked list can grow or shrink  its size during the execution of the program as per need.Hence no memory wastage occurs.
  • Structure is used in the creation of linked list which contains different data types that helps in making the record.
  • A linked list can be made just as long as required.
  • It helps to use exactly as much memory as they need by shrinking or expanding it.
  • It is used to maintain a dynamic series of data.
  • The use of pointer in a list reduces/eliminates the need for whole movement of data in memory during basic operations such as insertion, deletion, sorting etc. and saves time. Thus, a list  maintains data items in logical order than a physical order.

Basic Operations in a Linked List

There are following operations performed in a typical linked list –

  • Creation of the List/Linked list.
  • Traversing/Printing the list.
  • Counting the nodes in the list.
  • Inserting new nodes in the list.
  • Deleting existing nodes from the list.
  • Editing/Modifying/Updating the list.
  • Searching individual/specific data items from the list.
  • Sorting the list.
  • Merging/Concatenating the list.
  • Splitting the list.

    Advantages/Merits

    Linked lists have many advantages. Some of the very important advantages are : –

    • Linked lists are dynamic data structures. i.e. they can grow or shrink during the execution of a program as per need.
    • Linked lists have efficient memory utilization i.e., Here, memory is not pre-allocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
    • Insertion and Deletions are easier and efficient than array i.e. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.
    • Many complex applications can be easily carried out with linked lists.

    Disadvantages/Demerits

    • To access to any arbitrary item or data in a linked list is little cumbersome and time consuming.
    • Searching a particular element in list is difficult and also time consuming.
    • It consumes more space than an array with the same number of items because every node requires a additional pointer/ link field to store address of the next node.

    Use/Applications of Linked List

    There are following use of linked list in our life. These are –

    • To represent and manipulate polynomial form of structure as 
                      P(x) = a0  Xn + a1  Xn-1 + …… + an-1 X + an
    • To represent very large numbers in the memory.
    • To do operations of heavy number such as addition, multiplication and division.
    • To implement stack, queue, trees and graphs data structures for specific work.
    • To implement symbol table in compiler construction

    Types of Linked List

    There are three main types of linked list. These are –

    (A) Single/Singly/Linear/Simple linked list

    (B) Double/Two way linked list

    (C) Circular linked list – two types

    (a) Single Circular linked list.

    (b) Double Circular linked list.

    (A) Single linked list

    Definition

      • A single linked list is one in which all nodes are linked together by single link in some sequential manner. Hence, it is also called as linear linked list.

    Features

      • A linked list allocates space for each element separately in its own block of memory called a “node”.
      • The list gets an overall structure by using pointers to connect all its nodes together like the links in a chain.
      • Each node contains two fields; a “data” field to store whatever data/element, and a “address” field which is a pointer used to link to the next node.
      • Each node is allocated in the heap using malloc() function, so the node memory
        continues to exist until it is explicitly de-allocated using free().
      • The very first/front/beginning of the list is a pointer that store the address of first node of the linked list. It is popularly called ‘start’ pointer.This “start” pointer which points to the first node. The first node contains a pointer to the second node. The second node contains a pointer to the third node, … and so on. The last node in the list has its next field set to NULL to mark the end of the list.
      • Code in a linked list can access any node in the list by starting at the start pointer and following the next pointers. The start pointer is an ordinary local pointer variable, is in the form of stack. The list nodes of a  linked list are allocated in the form of heap.

    Syntax/Declaration

    struct tag-name
    {
    Datatype member 1;
    Datatype member 2;
    .
    .
    .
    Datatype member n;
    struct tag-name *pointer;
    };

    Example

    struct student
    {
    int  rollno;
    char stuname[30];
    float fee;
    struct student *ptr;
    };

    Advantages

        • Simple to Implement.
        • Insertions and Deletions is done easily.
        • It has dynamic size i.e. not fixed/static i.e. it can be extended or reduced according to requirements.
        • Elements are normally stored in scattered form in the memory.
        • It is less expensive/cost-efficient.

    Disadvantages

    (B) Double linked list

    Definition

      • A double linked list is one in which all nodes are linked together by multiple/two links which helps in accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list. Thus, each node in a double linked list has two link fields (pointers) to point to the left node (previous) and the right node (next). This helps to traverse in forward direction and backward direction.

    Features

      • A double linked list is a two-way list in which all nodes have two links/address part. This helps in accessing both successor node and predecessor node from the given node position.
      • It provides bi-directional traversing.
      • Each node in a double linked list contains three fields –
        • Left link Part.
        • Data Part.
        • Right link Part.
        The left link points to the predecessor node and the right link points to the successor node. The data field stores the required data.

    Syntax/Declaration

    struct tag-name
    {
    struct tag-name *pointer1;
    Datatype member 1;
    Datatype member 2;
    .
    .
    .
    Datatype member n;
    struct tag-name *pointer2;
    };

    Example

    struct student
    {
    struct student *back;
    int  rollno;
    char stuname[30];
    float fee;
    struct student *next;
    };

    Advantages

        • In DLL, we can be traversed in both forward and backward direction hence searching is easy.
        • The insertion and deletion operation in DLL is more efficient than SLL.

    Disadvantages

        • Every node of DLL require extra space for an extra back pointer.
        • All operations require an extra pointer to be maintained.

    (C) Circular linked list

    Definition

        • A circular linked list is one, which has no beginning and no end.
        • Circular linked list is a linked list where all nodes are connected to form a circle.

    Features

        • There is no NULL in its end node.

    Advantages

        • In this linked list, any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again to complete the traversing.
        • Useful for implementation of queue because we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.
        • Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application.
        • Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

    Disadvantages

    Types

      • There are two types of circular linked list – (a) Single Circular Linked List (b)Double Circular Linked List

    (a) Single Circular Linked List

    Definition

      • A single linked list can be made a circular linked list by simply storing address of the very first node in the link field of the last node.

    Features

    Syntax/Declaration

    struct tag-name
    {
    Datatype member 1;
    Datatype member 2;
    .
    .
    .
    Datatype member n;
    struct tag-name *pointer;
    };

    Example

    struct student
    {
    int  rollno;
    char stuname[30];
    float fee;
    struct student *ptr;
    };

    Advantages

    Disadvantages

    (b) Double Circular Linked List

    Definition

      • A circular double linked list is one, which has both the successor pointer and predecessor pointer in the circular manner.

    Features

    Syntax/Declaration

    struct tag-name
    {
    struct tag-name *pointer1;
    Datatype member 1;
    Datatype member 2;
    .
    .
    .
    Datatype member n;
    struct tag-name *pointer2;
    };

    Example

    struct student
    {
    struct student *back;
    int  rollno;
    char stuname[30];
    float fee;
    struct student *next;
    };

    Advantages

    Disadvantages

     1,414 total views,  1 views today


    0 Comments

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.