Linked List in Python

Linked List in Python

June 16, 2018
7 minutes read time
1 likes
0 comments
486 times viewed


header image

Description

This article will guide you about implementing linked list in python. It discusses about the implementation of various functions associated with linked list data structure.

Content

Linked List

A linked list is a linear data structure where each element is a separate object. Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node.

linked_list__70.png


Creating a node

A node in linked list contains the data field and a pointer to the next node.

linked_list_node__30.png

class Node(object):
    """docstring for Node."""
    def __init__(self, data):
        super(Node, self).__init__()
        self.data = data
        self.next = None

Creating an empty linked list

empty_linked_list__25.png

class LinkedList(object):
    """docstring for LinkedList."""
    def __init__(self):
        super(LinkedList, self).__init__()
        self.head = None

Printing a linked list

def print_list(self):
    temp = self.head
    while(temp):
        print(temp.data)
        temp = temp.next

Pushing a new node at front

push_at_front_linked_list__70.png

def push(self, new_data):
    new_node = Node(new_data)
    new_node.next = self.head
    self.head = new_node

Driver Program

sll = LinkedList()
sll.push(15); sll.push(2); sll.push(7); sll.push(3)

print ('Linked List before( push(5)):')
sll.print_list()

print ('\nLinked List after( push(5)):')
sll.push(5)
sll.print_list()

Output

output_push.png


Appending a new node at back

append_at_back_linked_list__70.png

def append(self, new_data):
    new_node = Node(new_data)

    if self.head is None:
        self.head = new_node
        return

    last = self.head
    while(last.next):
        last = last.next

    last.next = new_node

Driver Program

sll = LinkedList()
sll.push(15); sll.push(2); sll.push(7); sll.push(3)
print ('Linked List before(append(5)):')
sll.print_list()

print ('\nLinked List after(append(5)):')
sll.append(5)
sll.print_list()

output_append_node.png


Pushing a new node at a given position

insert_at_position_linked_list__70.png

def insertAt(self, position, new_data):
    if(position==0):
        self.push(new_data)
        return

    prev_node = self.head
    while(prev_node.next and position-1!=0):
        prev_node = prev_node.next
        position -= 1

    if(position-1!=0):
        print("No suffiecient Element")
        return

    new_node = Node(new_data)
    new_node.next = prev_node.next
    prev_node.next = new_node

Driver Program

sll = LinkedList()
sll.push(15); sll.push(2); sll.push(7); sll.push(3)

print ('Linked List before( insertAt(2,5)):')
sll.print_list()

print ('\nLinked List after( insertAt(2,5)):')
sll.insertAt(2,5)
sll.print_list()

Output
output_insert_at.png


Deleting a node with given value

delete_node_linked_list__70.png

def delete(self, data):
    temp = self.head
    if(temp):
        if(temp.data==data):
            self.head = temp.next
            temp = None
            return

    while(temp):
        if(temp.data==data):
            break
        prev = temp
        temp = temp.next

    if(not temp):
        print("Data to be deleted not present")
        return

    prev.next = temp.next
    temp = None

Driver Program

sll = LinkedList()
sll.push(15); sll.push(2); sll.push(7); sll.push(3)

print ('Linked List before( delete(2)):')
sll.print_list()

print ('\nLinked List after( delete(2)):')
sll.delete(2)
sll.print_list()

Output
output_delete.png


Complete Driver Program

class Node(object):
    """docstring for Node."""
    def __init__(self, data):
        super(Node, self).__init__()
        self.data = data
        self.next = None


class LinkedList(object):
    """docstring for LinkedList."""
    def __init__(self):
        super(LinkedList, self).__init__()
        self.head = None

    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def insertAt(self, position, new_data):
        if(position==0):
            self.push(new_data)
            return

        prev_node = self.head
        while(prev_node.next and position-1!=0):
            prev_node = prev_node.next
            position -= 1

        if(position-1!=0):
            print("No suffiecient Element")
            return

        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    def append(self, new_data):
        new_node = Node(new_data)

        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while(last.next):
            last = last.next

        last.next = new_node

    def delete(self, data):
        temp = self.head
        if(temp):
            if(temp.data==data):
                self.head = temp.next
                temp = None
                return

        while(temp):
            if(temp.data==data):
                break
            prev = temp
            temp = temp.next

        if(not temp):
            print("Data to be deleted not present")
            return

        prev.next = temp.next
        temp = None

    def print_list(self):
        temp = self.head
        while(temp):
            print(temp.data, end="")
            print("---->", end="")
            temp = temp.next
        print("NULL")



sll = LinkedList()
sll.append(6)
sll.push(7)
sll.push(1)
sll.push(9)
sll.append(4)
sll.insertAt(2,8)
sll.delete(9)

print ('Created linked list is:')
sll.print_list()

Final Output
final_output.png


List of curated problems based on Linked List



We are done



Like this post

1   Like


Share this post on

Google Plus LinkedIn


About the author




Join the discussion

Nothing to preview

Post Comment



Comments