Linked list-1

Question

Concept of linked list

Answer 1

Ques. Linked List Implementation 

Answer :

Linked list :  A linked list is a linear data structure in which we are having  nodes and each node consist of data part and the next part , data part contains the value and the next part is having the reference of the next node . Each  Python does not have linked lists in its standard library.

Example : if a node consists of 34|10, it means that the value of the node is 30, while the next item is stored at the memory location "10".

Types of Linked List :

• Single Linked List
• Doubly Linked List
• Circular Linked List

ARRAY	LINKED LIST
It is a consistent set of a fixed number of data items.	It is an ordered set comprising a variable number of data items.
Specified during declaration.	No need to specify; grow and shrink during execution.
Element location is allocated during compile time.	Element position is assigned during run time.
Stores element  consecutively	Stores elements randomly
Direct or randomly accessed	Sequentially accessed
Binary search and linear search	linear search
less Memory required	More Memory required
Memory Utilization is Ineffective	Memory Utilization is Efficient

Advantages :

1. Dynamic data Structure .
2. Linked List can grow and shrink during run time.
3. Insertion and Deletion Operations are Easier
4. Efficient Memory Utilization
5. Faster Access time,can be expanded in constant time without memory overhead
6. Linear Data Structures can be easily implemented using Linked list

Disadvantages  :

1. They use more memory than arrays because of the storage used by their pointers.
2. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.
3. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
4. Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.

Applications : 

1. Stack
2. Queues
3. Graphs
4. hastables

How to create a node  in linked list : As we know that a node consist of two parts one is the data part and another is the next part that stores the address of next node .  Initially the next part of a node is empty .

class Node:        # Function to initialize the node object     def __init__(self, data):         self.data = data  # Assign data         self.next = None  # Initialize next as null    # Linked List class class LinkedList:          # Function to initialize the Linked List object     def __init__(self):          self.head = None

Insertion into a linked list : 

1. Insert node at first 
2. Insert node at last 
3. Insert a node after a given node 

Insert a node at first : 

To insert a node at beginning  we need a Function to insert a new node at the beginning

1. Create a newnode & assign value to the newnode
2. Make next of new Node as start
3. Move the start to point to newnode  

def insert_at_first(self,value):         newnode=node(value)         newnode.next=self.start         self.start=newnode

Insert a node at last :

1. Create a new node 
2. assign the value  and Set next part  as None 
3. If the Linked List is empty, then make the new node as start 
4. Else traverse till the last node  and then Change the next of last node
5. for traversing we need to make a start node as temp and then check next part of temp node and iterate untill it is null 

def insert_at_last(self,value):    #insert value in node         newnode=node(value)  #new node we want to create  and  put  a value         if(self.start==None):          #if start is none the linked list is  empty then              self.start=newnode      #new node will be inserted as the first node          else:  #we have store value of start in temp i.e copied data of start in temp ,temp is pointing to start node             temp=self.start                     while(temp.next!=None):                   temp=temp.next             temp.next=newnode

Insert a node after a given node : 

1. check if the given prev_node exists 
2. Create new node and assign value
3. Make next of newnode as next of prev_node 
4. make next of prev_node as newnode 

def insertAfter(self, prev_node, value):          if prev_node == None:              print("previous node must in LinkedList.")             return         newnode = node(value) #Create new node &assign value #Make next of new Node as next of prev_node            newnode.next = prev_node.next   #make next of prev_node as new_node            prev_node.next = newnode

Deletion of the node  : 

def delete_from_first(self):         if self.start==None:             print("linked list is empty")         else:             temp=self.start             self.start=self.start.next

For the complete program that uses all of the above methods to create a linked list CLICK HERE