uhbis

Once more unto the uhbis, dear friends!

Linked List Data Structure

A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.

Linked lists can be singly or doubly linked.

Singly linked list

A singly linked list would use a node with data and only one reference (link) to the next node.

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

Full implementation

Doubly linked list

A doubly linked list would use a node with data and two references (links) which would point to the next and previous nodes.

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

Full implementation

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

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

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            next_node = self.head
            while next_node.next:
                next_node = next_node.next
            next_node.next = Node(data)

    def push(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
    
    def insert(self, data, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1
                
            new_node = Node(data)
            if prev_node:
                prev_node.next = new_node
                new_node.next = next_node
            else:
                new_node.next = next_node
                self.head = new_node

    def pop(self):
        next_node = self.head
        prev_node = None
        while next_node.next:
            prev_node = next_node
            next_node = next_node.next
        prev_node.next = None
        return next_node.data
    
    def remove(self, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1

            if prev_node:
                prev_node.next = next_node.next
            else:
                self.head = next_node.next

    def reverse(self):
        prev_node = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev_node
            prev_node = current
            current = next_node

        self.head = prev_node
    
    def search(self, data):
        if not self.head:
            return "Not Found"
        else:
            next_node = self.head
            index = 0
            while next_node.data != data:
                next_node = next_node.next
                index += 1
                if not next_node:
                    return "Not Found"
            return index

    def sort(self):
        current_node = self.head
        next_node = None
        if not self.head:
            return
        else:
            while current_node:
                next_node = current_node.next

                while next_node:
                    if current_node.data > next_node.data:
                        current_node.data, next_node.data = next_node.data, current_node.data 
                    next_node = next_node.next
                
                current_node = current_node.next

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