Friday , July 21 2017
Home / Data Structures / What is Linked List

What is Linked List

A linked list is a non-sequential collection of data items. It is a dynamic data structure.
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.

Advantages of linked list :

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

  1. Linked lists are dynamic data structures. i.e., they can grow or shrink during
    the execution of a program.
  2. Linked lists have efficient memory utilization. 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.
  3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility
    in inserting a data item at a specified position and deletion of the data item
    from the given position.
  4. Many complex applications can be easily carried out with linked lists.

Disadvantages of linked list :

  1. It consumes more space because every node requires a additional pointer to
    store address of the next node.
  2. Searching a particular element in list is difficult and also time consuming.

Types of Linked Lists :

Basically we can put linked lists into the following four items:

1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
4. Circular Double Linked List.

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

A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node
(previous node) from any arbitrary node within the list. Therefore 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.

A circular linked list is one, which has no beginning and no end. 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.

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

Applications of linked list :

1. Linked lists are used to represent and manipulate polynomial. Polynomials are
expression containing terms with non zero coefficient and exponents. For
example:

P(x) = a0 Xn + a1 Xn-1 + …… + an-1 X + an

2. Represent very large numbers and operations of the large number such as
addition, multiplication and division.
3. Linked lists are to implement stack, queue, trees and graphs.
4. Implement the symbol table in compiler construction

About chandrashekhar

Hi Folks, you have reach this so far, that shows you like what you are learning. Then why don't you support us to improve for bettor tutorials by leaving your valuable comments and why not you keep in touch with us for latest updates on your favorite blog @ facebook , twitter , Or Google+ ,

Recommended

What is an Algorithm ?

An algorithm is a finite sequence of instructions, each of which has a clear meaning …

Leave a Reply

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