Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
community creator

How to implement stack and queue using linked list

Likith Narukurthi

Data Structures are used to store large amounts of data in an efficient and categorical manner. For example in lists, arrays, tuples, dictionaries, and sets.

We are now gonna look into Linear Data Structures:

  • Linked Lists
  • Stacks
  • Queues

Linked list

A linked list consists of nodes/elements where each element contains a data field and a reference to the next node in the list.

# the node class is used to create an element holder and the respective reference pointers. 
class Node: 
    def __init__(self, data=None, next=None):
        self.data = data  # the value part of the node
        self.next = next  # the pointer part of the node

# this is the main class that that is used to create the linked list data struture which contains many functions.
class LinkedList:
    def __init__(self):
        self.head = None  # creating an empty linked list
    # the below function is used to insert the nodes/element holders at the begining of the list
    def Insert_at_beginning(self, data):
        # creating a node with a data part and the pointer to the next value i.e . the now head
        node = Node(data, self.head)
        self.head = node  # now the head points towards the new inserted element pushing the previous element behind
    # the below function is used to insert the nodes/element holders at the ending of the list
    def Insert_at_ending(self, data):
        if self.head is None:
            self.head = Node(data)
            return
        itr = self.head
        while itr.next:
            itr = itr.next
        itr.next = Node(data)
    # this function inserts a list of values to the linked list at the end
    def insert_values(self, value_list):

        self.head = None

        for value in value_list:
            self.Insert_at_ending(value)
    # this function is used to get the length of the linked list.
    def get_length(self):
        count = 0
        itr = self.head
        while itr:
            count += 1
            itr = itr.next
        return count

    # the below function is used to insert a value just after an existing value in the list
    def insert_after_value(self, data_after, data_to_insert):
        if self.head is None:
            return

        if self.head.data == data_after:
            self.head.next = Node(data_to_insert, self.head.next)
            return

        itr = self.head
        while itr:
            if itr.data == data_after:
                itr.next = Node(data_to_insert, itr.next)
                break

            itr = itr.next
    # the below function is used to remove a particular value which in present in the list.
    def remove_by_value(self, data):
        if self.head is None:
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        itr = self.head
        while itr.next:
            if itr.next.data == data:
                itr.next = itr.next.next
                break
            itr = itr.next
    # this function simply orints all the values present inthe list.
    def display(self):
        if self.head is None:
            print('list is empty')
            return
        itr = self.head
        llstr = ''
        while itr:
            llstr += str(itr.data) + '-->'
            itr = itr.next
        print(llstr)


if __name__ == "__main__":
    ll = LinkedList()
    ll.insert_values(["banana", "mango", "grapes", "orange"])
    ll.display()
    ll.insert_after_value("mango", "apple")  # insert apple after mango
    ll.display()
    ll.remove_by_value("orange")  # remove orange from linked list
    ll.display()
    ll.remove_by_value("figs")
    ll.display()
    ll.remove_by_value("banana")
    ll.remove_by_value("mango")
    ll.remove_by_value("apple")
    ll.remove_by_value("grapes")

    ll.display()

Stacks using linked list

A stack is a linear data structure that follows a specific order.

The order may be:

  • LIFO(Last In First Out)
  • FILO(First In Last Out)

Here, you can only retrieve whichever element you enter first at the end and not in between.

There are many ways to implement a stack data structure, but we are gonna do it using a linked list.

# the node class is used to create an element holder and the respective reference pointers.
class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

# this is the main class that that is used to create queues data struture which contains many functions.
class Stack:
    # this is automatically class when an instance of the class is called.
    def __init__(self):
        self.top = None
    # the below function is used to append an value on the top of the stack.  
    def push(self, data):
        if self.top is None:
            self.top = Node(data, None)
            return
        self.top = Node(data, self.top)
    # the below function is used to remove an value from the top of the stack.
    def pop(self):
        if self.top is None:
            return
        temp = self.top
        if self.top is not None:
            self.top = self.top.next
        temp.next = None
        return temp.data
    # the below function returns the value on the top of the stack.  
    def peek(self):
        return self.top.data
    # this function simply clears the whole stack.
    def clearstack(self):
        self.top = None
    # the below tells us if the stack is empty.
    def emptystack(self):
        if self.top is None:
            return True
        return False
    # this below function is used print out the stacks.
    def display(self):
        itr = self.top
        sstr = ' '
        while itr:
            sstr += str(itr.data) + '-->'
            itr = itr.next
        print(sstr)

if __name__ == "__main__":
    stack = Stack()
    stack.push(10)
    stack.push(20)
    stack.push(40)
    stack.peek()
    stack.display()
    stack.pop()
    stack.push(30)
    stack.display()
    stack.clearstack()
    stack.display()

Queues using linked list

A queue is also a linear structure that follows a specific order.

The order is:

  • First In First Out (FIFO)

The difference between stacks and queues is how they are removed. In a stack, we remove the item most recently added; in a queue, we remove the item least recently added.

There are many ways to implement a queue data structure, but we are going to do it using a linked list.

# the node class is used to create an element holder and the respective reference pointers. 
class Node:
    def __init__(self, data=None, next=None, prev=None):
        self.data = data #creating a storage for assigning value
        self.next = next #pointer to the next value
        self.prev = prev #pointer to the already existing previous value.

# this is the main class that that is used to create queues data struture which contains many functions.
class Queue:
    # this is automatically class when an instance of the class is called.
    def __init__(self): 
        self.front = self.rear = None 
    # this below function is used to append a value at the end of the queue which is similar to a late comer joins at the end.  
    def enqueue(self, data):
        if self.rear is None:
            self.front = self.rear = Node(data, None)
            return

        self.rear.next = Node(data, None)
        self.rear.next.prev = self.rear
        self.rear = self.rear.next
    # this below function is used remove a value from the start of the queue.
    def dequeue(self):
        if self.front is None:
            raise Exception('empty queue')
        temp = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
            return
        self.front.prev = None

        return temp
    # this code is used to clear the whole queue
    def clearqueue(self):
        self.front = self.rear = None
    # this is used to check idf the queue in empty or not.
    def emptyqueue(self):
        if self.front is None:
            return True
        return False
    # this is used to print queues
    def display(self):
        itr = self.front
        sstr = ' '
        while itr:
            sstr += str(itr.data) + '-->'
            itr = itr.next
        print(sstr)


if __name__ == "__main__":
    queue = Queue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    queue.display()
    queue.dequeue()
    queue.dequeue()
    queue.dequeue()
    queue.display()
    queue.enqueue(40)
    queue.enqueue(50)
    queue.enqueue(60)
    queue.display()
    queue.clearqueue()
    queue.display()

RELATED TAGS

python
community creator
RELATED COURSES

View all Courses

Keep Exploring