Chapter: Linked List

INTRODUCTION

Generally the daily life term “list” refers to the linear collection of data,whether the list may be shopping list,a daily routine, invitation list,a schedule,a meeting plan,a grocer’s list.If you want to insert any item in the list simply what you do is:delete that and insert any new item wherever n whenever you want.You can extend,add,remove,modify any item at any time with no constraints in your list.
One such way we know is we can implement list with arrays but why list lets know.

What is need of Linked list?

Well we know how arrays work and the representation of arrays in contiguous memory locations.You have also considered the problems
associated with arrays:-

  • If there is not enough memory available for allocation??
  • If you have to insert the data in sorted order??
  • If you want to insert the item at any location??
  • If you want to create your list dynamically??
  • If you want to delete any item at any location??
  • If you want to insert the data of different data types??

Well the above problems are not every time associated with your programming but the Linked list is the smartest way to solve above problems.With arrays we have to make a “for loop” taking the time equal to the size of the arrays. Even if there enough memory spaces available for allocation but not in contiguous manner, your program crashes but with Link list it won’t happen.That’s why Linked list comes into picture and is of great use.

DEFINITION

A linked list is a linear collection of data items called nodes and each node is connected to another node with the help of pointers,a node is divided into two subparts first for storing the data item and another for storing the address of the next node.The pointer stores the address and forms a link between two nodes thus this representation to store the data is called Linked list.

Memory representation of linked list

Linked list is not stored in the contiguous memory locations.Each node contains the link of next node,so the nodes can be created in the memory irrespective of the order of the data items.

Is linked list a linear data structure or non linear?

This is the best question asked by the interviewer whether a Linked list is a linear data structure or not because there is controversy and usually student’s get confused.
Yes, the Linked list is a linear data structure.We have seen the memory representation of linked list it is not stored in contiguous memory allocation but while accessing each item in a linked list we move in a linear way.That’s why it is called a Linear data structure.

Operations on linked list

Traversal
Accessing each element in the list is called traversal . A particular process is applied to the data whether addition,division, subtraction,or even just printing the data elements.
Insertion
Adding a data element into the list is called insertion.Insertion can be dynamic, in the middle, at end, at beginning.
Deletion
Removing a data element from the list is called deletion. Deletion can be at end,after some element, at beginning.
Searching
Finding a particular element in the list is called searching.

Types of linked list

  1. SINGLY LINKED LIST
  2. DOUBLY LINKED LIST
  3. CIRCULAR LINKED LIST
  4. HEADER LINKED LIST

SINGLY LINKED LIST

Each node may contain one or more data fields but there is only one pointer field in the node.We can only move forward in singly linked list not in backward direction.The last node may or may not contain a null pointer.

DOUBLY LINKED LIST

In doubly linked list each node contains the data items as well as pointers to the previous node and next node.Deletion of a node after or before some location is comparatively very easy.We can move in both direction either beginning to end or end to beginning.It is also called TWO way linked list.

CIRCULAR LINKED LIST

In circular linker list the pointer of the last node is linked to either the first node or the header node forming a circle.A circular linked list can be.

  • One way circular linked list
  • Two way circular linked list

HEADER LINKED LIST

A header linked list contains an extra node called the head of the linked list.This head contains the important information may be about the number of elements either whole,positive or negative.The header node can contain the extra number of data items as compared to the other node.
A header linked list are of types:

  • Grounded header linked list
  • Circular header linked list
  • Two-way grounded header linked list
  • Two-way circular header linked list

ADVANTAGES OF LINKED LIST

  1. Easy insertion and deletions implementation:-No need to shift the data as in arrays.
  2. Collection of non-homogeneous data as well as nodes.
  3. Linked lists are dynamic data structure, allocating the needed memory while the program is running.
  4. Linear data structure like stacks and queues are easily executed by Linked lists.
  5. Header node helps to reduce complexity as it contains an important information in its data field.
  6. Deletion of any node before or after or at a location is easy with Linked list.
  7. No contiguous memory allocation requires.
  8. Insertion in sorted order is easily implemented with linked list.
  9. Whenever there is frequent changes in the list ,Linked list is preferred due to less complexity issues.
  10. It can be used to represent the polynomial expression
    it means polynomial=4x3+6x2+10x1+6x0in some cases there are 5 terms but array requires 50 memory allocations such as poly=6x49+4x34+6x40+10x1+6x0

DISADVANTAGES OF LINKED LIST

  1. The link pointer in the node acquires extra memory space.
  2. The traversing is in sequential order.
  3. Nodes are not indexed.
  4. Binary search is not applicable in Linked list.
  5. Singly linked list can be accessed only from beginning to end not in reverse manner.
  6. We can’t access the middle element of the list directly.

Click to download the program for the implementation of linked list

 

Author: Sonia Behal

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s