DSA

Linked List
A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.

The following code is designed as follows :

1. Class "Node" to declare pointers.

2. Class "Linked List" to design methods which will help user to perform desired operation over their Linked List data structure.

3. Sample Driver Code to demonstrate the functioning of the template.



class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None

    def print(self):
        if self.head is None:
            print("Linked is empty")
            return
        # itr = current node, itr.next = next node of current node
        itr = self.head
        llstr = ''
        while itr is not None:
            llstr += str(itr.data) + '---->'
            itr = itr.next

        print(llstr)

    def insert_at_begining(self, data):
        node = Node(data, self.head)
        self.head = node

    def insert_at_end(self, data):
        if self.head is None:
            self.head = Node(data, None)
            return

        itr = self.head
        while itr.next:
            itr = itr.next

        itr.next = Node(data, None)

    def insert_values(self, data_list):
        self.head = None
        for data in data_list:
            self.insert_at_end(data)

    def count_nodes(self):
        counter = 0
        itr = self.head
        while itr:
            counter += 1
            itr = itr.next

        return counter

    def remove_node(self, index):
        if index < 0 or index > self.count_nodes():
            raise Exception(" Out of bound index")

        if index == 0:
            self.head = self.head.next
            return

        counter = 0
        itr = self.head
        while itr:
            if counter == index - 1:
                itr.next = itr.next.next
                break

            itr = itr.next
            counter += 1

    def insert_value_at(self, index, data):
        if index < 0 or index > self.count_nodes():
            raise Exception(" Out of bound index")

        if index == 0:
            self.insert_at_begining(data)
            return

        count = 0
        itr = self.head
        while itr:
            if count == index - 1:
                node = Node(data, itr.next)
                itr.next = node
                break

            itr = itr.next
            count += 1


if __name__ == "__main__":
    llist = LinkedList()
    llist.insert_values(["vadapav", "samosa", "chutney", "dosa", "chowmin"])
    llist.print()
    llist.count_nodes()
    print("Total nodes = ", llist.count_nodes())

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

Major differences between array and linked-list are listed below:

Size : Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to the risk of overwriting other data. However, in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size that can change at runtime.

Memory allocation: For arrays at compile time and at runtime for linked lists. but, a dynamically allocated array also allocates memory at runtime.

Memory efficiency : For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; Memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.

Execution Time : Any element in an array can be directly accessed with its index. However, in the case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while others (such as inserting/deleting an element in the data) are faster in linked lists.

Insertion : In an array, insertion operation takes more time but in a linked list these operations are fast. For example, if we want to insert an element in the array at the end position in the array and the array is full then we copy the array into another array and then we can add an element whereas if the linked list is full then we find the last node and make it next to the new node Dependency: In an array, values are independent of each other but In the case of linked list nodes are dependent on each other. one node is dependent on its previous node. If the previous node is lost then we can’t find its next subsequent nodes.

Doubly Linked List
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

The following code is designed as follows :

1. Class "Node" to declare pointers. This Node class is as same as Singly Linked List but with extra pointer i.e "prev" which is precious pointer.

2. Class "Doubly Linked List" to design methods which will help user to perform desired operation over their Doubly Linked List data structure.

3. Sample Driver Code to demonstrate the functioning of the template.



class Node:
def __init__(self, data=None, next=None, prev=None):
    self.data = data
    self.next = next
    self.prev = prev


class DoublyLinkedList:
def __init__(self):
    self.head = None

def print_forward(self):
    if self.head is None:
        print("Linked list is empty")
        return
    itr = self.head
    llstr = ''
    while itr:
        llstr += str(itr.data)+' --> ' if itr.next else str(itr.data)
        itr = itr.next
    print(llstr)

def print_backward(self):
    if self.head is None:
        print("Linked list is empty")
        return

    last_node = self.get_last_node()
    itr = last_node
    llstr = ''
    while itr:
        llstr += itr.data + '-->'
        itr = itr.prev
    print("Link list in reverse: ", llstr)

def get_last_node(self):
    itr = self.head
    while itr.next:
        itr = itr.next

    return itr

def get_length(self):
    count = 0
    itr = self.head
    while itr:
        count += 1
        itr = itr.next

    return count

def insert_at_begining(self, data):
    node = Node(data, self.head)
    self.head = node

def insert_at_end(self, data):
    if self.head is None:
        self.head = Node(data, None)
        return

    itr = self.head

    while itr.next:
        itr = itr.next

    itr.next = Node(data, None)

def insert_at(self, index, data):
    if index < 0 or index > self.get_length():
        raise Exception("Invalid Index")

    if index == 0:
        self.insert_at_begining(data)
        return

    count = 0
    itr = self.head
    while itr:
        if count == index - 1:
            node = Node(data, itr.next)
            itr.next = node
            break

        itr = itr.next
        count += 1

def remove_at(self, index):
    if index < 0 or index >= self.get_length():
        raise Exception("Invalid Index")

    if index == 0:
        self.head = self.head.next
        return

    count = 0
    itr = self.head
    while itr:
        if count == index - 1:
            itr.next = itr.next.next
            break

        itr = itr.next
        count += 1

def insert_values(self, data_list):
    self.head = None
    for data in data_list:
        self.insert_at_end(data)

def insert_after_value(self, data_after, data_to_insert):
    # Search for first occurance of data_after value in linked list
    # Now insert data_to_insert after data_after node
    itr = self.head
    while itr:
        if data_after == itr.data:
            node = Node(data_to_insert, itr.next)
            itr.next = node
            break
        itr = itr.next

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


if __name__ == '__main__':
ll = DoublyLinkedList()
ll.insert_values(["banana", "mango", "grapes", "orange"])
ll.get_last_node()
ll.print_backward()

A Doubly Linked List (DLL) contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list.

Advantages of DLL over the singly linked list:

DLL can be traversed in both forward and backward directions.

The delete operation in DLL is more efficient if pointer to the node to be deleted is given.

We can quickly insert a new node before a given node.

In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using the previous pointer.

Disadvantages of DLL over the singly linked list:

Every node of DLL Requires extra space for a previous pointer. It is possible to implement DLL with a single pointer though

All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with the next pointers. For example in the following functions for insertions at different positions, we need 1 or 2 extra steps to set the previous pointer.

Applications of Doubly Linked List:

For implementation of undo functionality at many places like editors, photoshop.
In file systems.
In Undo stacks.
In both forward and backward traversal of a list.

Stack - - -> (using Linked List)
A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.

The following code is designed as follows :

1. Class "Element" to declare pointers..

2. Class "Linked List" to design methods which will help user to perform desired operation over their Stack data structure.

3. Class Stack to create basic stack operations i.e push and pop



class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        "Insert new element as the head of the LinkedList"
        new_element.next = self.head
        self.head = new_element

    def delete_first(self):
        "Delete the first (head) element in the LinkedList as return it"
        if self.head:
            deleted_element = self.head
            temp = self.head.next
            self.head = temp
            return deleted_element
        else:
            return None


class Stack(object):
    def __init__(self, top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):
        "Push (add) a new element onto the top of the stack"
        self.ll.insert_first(new_element)

    def pop(self):
        "Pop (remove) the first element off the top of the stack and return it"
        return self.ll.delete_first()


# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a Stack
stack = Stack(e1)

# Test stack functionality
stack.push(e2)
stack.push(e3)
print(stack.pop().value)
print(stack.pop().value)
print(stack.pop().value)
print(stack.pop())
stack.push(e4)
print(stack.pop().value)

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.

Queue - - -> (using Linked List)
Like stack, queue is a linear data structure that stores items in First In First Out (FIFO) manner. With a queue the least recently added item is removed first. A good example of queue is any queue of consumers for a resource where the consumer that came first is served first.

The following code is designed as follows :

1. Imported"deque" from collections.

2. Class "Queue" to perform enqueue, dequeue and peek operation

3. Driver code to demonstrate the queue operation.



from collections import deque


class Queue:
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        self.storage.append(new_element)

    def peek(self):
        return self.storage[0]

    def dequeue(self):
        return self.storage.pop(0)


# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print(q.peek())

# Test dequeue
# Should be 1
print(q.dequeue())

# Test enqueue
q.enqueue(4)
# Should be 2
print(q.dequeue())
# Should be 3
print(q.dequeue())
# Should be 4
print(q.dequeue())
q.enqueue(5)
# Should be 5
print(q.peek())

A queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.

FIFO Principle of Queue:

A Queue is like a line waiting to purchase tickets, where the first person in line is the first person served. (i.e. First come first serve).

A Queue is like a line waiting to purchase tickets, where the first person in line is the first person served. (i.e. First come first serve).

Operations on Queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

Front: Get the front item from queue.

Rear: Get the last item from queue.

Characteristics of Queue:

Queue can handle multiple data.

We can access both ends.

They are fast and flexible.

Queue Representation:
Like stacks, Queues can also be represented in an array: In this representation, the Queue is implemented using the array. Variables used in this case are

Queue: the name of the array storing queue elements.

front: the index of the front element of the queue.

rear: the index of the rear element of the queue.

size: the size of the queue.

Design of the Template

Explanation <\>

Design of the Template

Explanation <\>

Design of the Template

Explanation <\>

Design of the Template

Explanation <\>