Linked List

first we must know what a node is;

the linked list is a dynamic data structure in which each element points to the next. the number of nodes in this list can grow and shrink, i.e. it is not fixed. This data structure is one of the simplest and most common, and it can be used to implement many other types of data (for example in hash tables). it has several advantages and disadvantages with respect to an array, but the main advantage of a linked list is that the elements of the list can be easily inserted or deleted without reassigning or reorganizing the whole structure.
##Node the node that works in the linked list has 2 data, the value and the reference to the other node as shown in the picture

This is how it could be implemented

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

Implementation linked list:


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


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

    def append(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = self.head
            self.length = 1
        else:
            self.tail.next = new_node
            self.tail = new_node
            self.length += 1

    def prepend(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = self.head
            self.length += 1
        else:
            new_node.next = self.head
            self.head = new_node
            self.length += 1

    def print_list(self):
        if self.head == None:
            print("Empty")
        else:
            current_node = self.head
            while current_node!= None:
                print(current_node.data, end= ' ')
                current_node = current_node.next
        print()

    def insert(self, position, data):
        if position >= self.length:
            if position>self.length:
                print("This position is not available. Inserting at the end of the list")
            new_node = Node(data)
            self.tail.next = new_node
            self.tail = new_node
            self.length += 1
        elif position == 0:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
            self.length += 1
        else:
            new_node = Node(data)
            current_node = self.head
            for i in range(position-1):
                current_node = current_node.next
            new_node.next = current_node.next
            current_node.next = new_node
            self.length += 1


    def delete_by_value(self, data):
        if self.head == None:
            print("Linked List is empty. Nothing to delete.")
            return
        current_node = self.head
        if current_node.data == data:
            self.head = self.head.next
            if self.head == None or self.head.next==None:
                self.tail = self.head
            self.length -= 1
            return
        while current_node.next!= None and current_node.next.data != data:
            current_node = current_node.next
        if current_node.next!=None:
            current_node.next = current_node.next.next
            if current_node.next == None:
                self.tail = current_node
            self.length -= 1
            return
        else:
            print("Given value not found.")

    def delete_by_position(self, position):
        if self.head == None:
            print("Linked List is empty. Nothing to delete.")
            return
        if position == 0:
            self.head = self.head.next
            if self.head == None or self.head.next == None:
                self.tail = self.head
            self.length -= 1
            return
        if position>=self.length:
            position = self.length-1
        current_node = self.head
        for i in range(position - 1):
            current_node = current_node.next
        current_node.next = current_node.next.next
        self.length -= 1
        if current_node.next == None:
            self.tail = current_node
        return

Doubly Linked List

Unlike a normal linked list in which in each node there was a reference to the next node in a doubly linked list in each node there are 2 references, one to the next node and one to the previous one. By having 2 references it spends more memory and although it has the same algorithmic complexity it can be seen that it is a little faster in some aspects, since for example to arrive to the penultimate element instead of going through almost the whole list it will only go through the last one.

the only thing that would have to be done to implement the above list and turn it into a Doubly linked list would be to add a new property to the node and change a little the functions of the classes to notice the difference between a doublyLinkedList and a LinkedList. So we can make a doubly linked list just by having the previous linked list. So:

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

    def print_list(self):
        if self.head == None:
            print("Empty")
        else:
            current_node = self.head
            while current_node!= None:
                print(current_node.data, end= ' ')
                current_node = current_node.next
        print()


    def append(self, data):
        new_node = Node(data)
        if self.head == None: 
            self.head = new_node
            self.tail = self.head
            self.length += 1
            return
        else: 
            new_node.previous = self.tail
            self.tail.next = new_node 
            self.tail = new_node 
            self.length += 1
            return

    def prepend(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = self.head
            self.length += 1
            return
        else:
            new_node.next = self.head 
            self.head.previous = new_node 
            self.head = new_node 
            self.length += 1
            return


    def insert(self, position, data):
        if position == 0:
            self.prepend(data) 
            return
        if position >= self.length:
            self.append(data) 
            return
        else:
            new_node = Node(data)
            current_node = self.head
            for i in range(position - 1): 
                current_node = current_node.next
            new_node.previous = current_node 
            new_node.next = current_node.next 
            current_node.next = new_node 
            new_node.next.previous = new_node 
            self.length += 1
            return


    def delete_by_value(self, data):
        if self.head == None:
            print("Linked List is empty. Nothing to delete.")
            return

        current_node = self.head
        if current_node.data == data:
            self.head = self.head.next
            if self.head == None or self.head.next==None: 
                self.tail = self.head
            if self.head != None:
                self.head.previous = None 
            self.length -= 1
            return
        try:  
            while current_node!= None and current_node.next.data != data:
                current_node = current_node.next
            if current_node!=None:
                current_node.next = current_node.next.next
                if current_node.next != None: 
                    current_node.next.previous = current_node 
                else:
                    self.tail = current_node 
                self.length -= 1
                return
        except AttributeError:
            print("Given value not found.")
            return


    def delete_by_position(self, position):
        if self.head == None:
            print("Linked List is empty. Nothing to delete.")
            return

        if position == 0:
            self.head = self.head.next
            
            if self.head == None or self.head.next == None:
                self.tail = self.head
            if self.head != None:
                self.head.previous = None 
            self.length -= 1
            return

        if position>=self.length:
            position = self.length-1

        current_node = self.head
        for i in range(position - 1):
            current_node = current_node.next
        current_node.next = current_node.next.next
        if current_node.next != None: 
            current_node.next.previous = current_node
        else:
            self.tail = current_node
        self.length -= 1
        return