Linked List Introduction

LINKED LISTS:

A dynamic data structure that allocates and de-allocates memory during run-time of a program on every addition and deletion of an element. The linked list is a linear collection of data elements called nodes pointing to the next node by means of a pointer.in all space for each data item is obtained as and when needed and each item is connected or linked to the next data item using a pointer.it is not necessary that memory space is allocated contiguously or located in adjacent memory location rather they can be scattered anywhere in memory.

each node is divided into two parts the first the information of element, the second part called the linker next [pointer containing the address of the next node in the list.

MEMORY ALLOCATION USED:

each data element stored in memory is given some memory (main memory). the main memory can also be allocated in manner:

this memory allocation technique facilitates allocation of memory during the program execution itself as and when required the technique of memory allocation is called dynamic memory allocation it also facilitates the release of memory if memory is not required any more data structures like linked list and trees use this for memory allocation

EXAMPLE:

Struct node

{

int roll number;

Node*next;

}

Function create a new node

 

Node create_newnode(int n)

{

Node*ptr; 

ptr = newNode

Ptr ->roll number;

ptr ->next = null;

return ptr;

}

Advantages of linked lists:

 Linked lists have many advantages.

• Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program. 
• 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. 
• 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. 
• Many complex applications can be easily carried out with linked lists. 

Disadvantages of linked lists: 

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

Types of Linked Lists:

• Linear linked list or one way linked list or a single list
• Double Linked List
• Circular Linked List.
• Circular Double Linked List.

What linked lists are and are not good for:

Linked lists are good for any task that involves inserting or deleting elements next to an element you already have a pointer to; such operations can usually be done in O(1) time. They generally beat arrays (even resizeable arrays) if you need to insert or delete in the middle of a list since an array has to copy any elements above the insertion point to make room; if inserts or deletes always happen at the end, an array may be better.

Linked lists are not good for any operation that requires random access, since reaching an arbitrary element of a linked list takes as much as O(n) time. For such applications, arrays are better if you don’t need to insert in the middle; if you do, you should use some sort of trees.