Gadgets 4 Students Career Guide Free Tutorials  Go to Your University  Placement Preparation 
0 like 0 dislike
472 views

1 Answer

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited by
 
Best answer

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
ARRAYLINKED 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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory
...