Source code for pygorithm.data_structures.linked_list

"""
Author: OMKAR PATHAK
Created On: 5th August 2017

Linked l_list and Node can be accommodated
in separate classes for convenience
"""
import inspect


[docs]class Node(object): """ Node class for creating a node for linked list. Each node has its data and a pointer that points to next node in the Linked l_list """ def __init__(self, data, next_node=None): """ constructor :param data: :param next_node: """ self.data = data self.next = next_node
[docs] @staticmethod def get_code(): """ return the code for the current class """ return inspect.getsource(Node)
[docs]class SinglyLinkedList(object): """ Defining the head of the linked list """ def __init__(self): """ constructor """ self.head = None def _search(self, node, data): """ searches the node, if valid returns the node else return false """ if node is None: return False if node.data == data: return node return self._search(node.next, data)
[docs] def get_data(self): """ prints the elements in the linked list """ temp = self.head l_list = [] while temp: l_list.append(temp.data) temp = temp.next return l_list
[docs] def insert_at_start(self, data): """ insert an item at the beginning of the linked list """ if self.head is None: new_node = Node(data) self.head = new_node else: new_node = Node(data) new_node.next = self.head self.head = new_node
[docs] def insert_after(self, next_node_data, data): """ insert an item after an element in the linked list """ new_node = Node(data) current_node = self._search(self.head, next_node_data) new_node.next = current_node.next current_node.next = new_node
[docs] def insert_at_end(self, data): """ insert an item at the end of the linked list """ new_node = Node(data) temp = self.head # get last node while temp.next is not None: temp = temp.next temp.next = new_node
[docs] def delete(self, data): """ to delete specified element from the linked list """ temp = self.head # if data/key is found in head node itself if temp is not None: if temp.data == data: self.head = temp.next return else: # else search all the nodes while temp.next is not None: if temp.data == data: break # save current node as previous so that we can go on to next node prev = temp temp = temp.next # node not found if temp is None: return # TODO: local variable 'prev' might be referenced before assignment # TODO: Fix this prev.next = temp.next return
[docs] @staticmethod def get_code(): """ return the code for the current class """ return inspect.getsource(SinglyLinkedList)
[docs]class DoublyLinkedList(object): """DoublyLinkedList DoublyLinkedList Class """ def __init__(self): """ constructor """ self.head = None
[docs] def get_data(self): """ prints the elements in the linked list """ temp = self.head l_list = [] while temp: l_list.append(temp.data) temp = temp.next return l_list
[docs] def insert_at_start(self, data): """ insert an element at the beginning of the linked list """ if self.head is None: self.head = Node(data) else: new_node = Node(data) self.head.previous = new_node new_node.next = self.head self.head = new_node
[docs] def insert_at_end(self, data): """ insert an element at the end of the linked list """ new_node = Node(data) temp = self.head while temp.next is not None: temp = temp.next temp.next = new_node new_node.previous = temp
[docs] def delete(self, data): """ to delete specified element from the linked list """ temp = self.head if temp.next is not None: # if head node is to be deleted if temp.data == data: temp.next.previous = None self.head = temp.next temp.next = None return else: while temp.next is not None: if temp.data == data: break temp = temp.next if temp.next: # if element to be deleted is in between temp.previous.next = temp.next temp.next.previous = temp.previous temp.next = None temp.previous = None else: # if element to be deleted is the last element temp.previous.next = None temp.previous = None return if temp is None: return
[docs] @staticmethod def get_code(): """ returns the code of the current class """ return inspect.getsource(DoublyLinkedList)
class CircularLinkedList(object): ''' Class for circular linked list ''' def __init__(self): self.head = None self.tail = None self.size = 0 def clear(self): ''' clears the head and tails of the linked list ''' self.tail = None self.head = None def get_data(self): """ prints the elements in the linked list """ l_list = [] current = self.tail while True: l_list.append(current.data) current = current.next if current == self.tail: break return l_list def insert(self, data): ''' inserts the data in to the linked list ''' node = Node(data) if self.head: self.head.next = node self.head = node else: self.head = node self.tail = node self.head.next = self.tail self.size += 1 def delete(self, data): ''' deletes the specified element from linked list ''' current = self.tail prev = self.tail while prev == current or prev != self.head: if current.data == data: if current == self.tail: self.tail = current.next self.head.next = self.tail else: prev.next = current.next self.size -= 1 return prev = current current = current.next @staticmethod def get_code(): """ returns the code of the current class """ return inspect.getsource(CircularLinkedList) if __name__ == '__main__': cll = CircularLinkedList() cll.insert(1) cll.insert(2) cll.insert(3) print(cll.get_data())