Single Linked List

Data Structures And Algorithms Note

Basic Initialize

# Node class
class Node:

    # Function to initialize the node object
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None  # Initialize next as null

# Linked List class
class LinkedList:
  
    # Function to initialize the Linked List object
    def __init__(self): 
        self.head = None

Function for push new node and delete node

# Linked List class
class LinkedList:
  
    # Function to initialize the Linked List object
    def __init__(self): 
        self.head = None
        
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
    def deleteNode(self, key): 
        # Store head node 
        temp = self.head
        
        # if head node holds the key to be deleted
        if temp is not None:
            if temp.data == key:
                self.head = temp.next
                return
        
        # go through each node until find the key,
        # keep track of previous node
        while temp is not None:
            if temp.data == key:
                break
            prev = temp
            temp = temp.next
            
        # if key was not in linked list (while loop stop)
        if temp is None:
            return
        
        # unlink the node from linked list
        prev.next = temp.next
        
    def printList(self): 
        temp = self.head 
        while temp: 
            print(temp.data)
            temp = temp.next

how it works

llist = LinkedList() 
llist.push(7) 
llist.push(1) 
llist.push(3) 
llist.push(2) 
print ("Created Linked List: ")
llist.printList() 
llist.deleteNode(1) 
print ("\nLinked List after Deletion of 1:")
llist.printList()
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Created Linked List: 
2
3
1
7
Linked List after Deletion of 1:
2
3
7

how I would do

class Node:
    # Function to initialize the node object
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None  # Initialize next as null

class LinkedList:
    # Function to initialize the Linked List object
    def __init__(self): 
        self.head = None
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
        
    def swapnodes(self, x, y):
        # find Node x
        tempx = self.head
        while tempx is not None:
            if tempx.data == x:
                break
            prevx = tempx
            tempx = tempx.next
        # find Node y
        tempy = self.head
        while tempy is not None:
            if tempy.data == y:
                break
            prevy = tempy
            tempy = tempy.next
        # swap next pointers
        prevx.next, prevy.next = tempy, tempx
        tempy.next, tempx.next = tempx.next, tempy.next
        
    def printList(self): 
        temp = self.head 
        while temp: 
            print(temp.data)
            temp = temp.next

for example

llist = LinkedList()
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print('origin')
llist.printList()
llist.swapnode(4, 3)
print('new')
llist.printList()
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
origin
1
2
3
4
5
new
1
2
4
3
5

think about the edge cases

• x and y may or may not be adjacent
• Either x or y may be a head node.
• Either x or y may be the last node.
• x and/or y may not be present in the linked list.

def swapnode(self, x, y):
        # do nothing when x and y are same
        if x == y:
            return
        
        # set prevx as None to define Node x is head or not
        prevx = None
        tempx = self.head
        while tempx is not None:
            if tempx.data == x:
                break
            prevx = tempx
            tempx = tempx.next
            
        # set prevy as None to define Node y is head or not
        prevy = None
        tempy = self.head
        while tempy is not None:
            if tempy.data == y:
                break
            prevy = tempy
            tempy = tempy.next
        # Node x or Node y not exist, do nothing
        if tempx is None or tempy is None:
            return
        
        # when prevx is not head, set prevx.next to tempy
        if prevx is not None:
            prevx.next = tempy
        # otherwise, prevx is None
        # set tempy as the new head directly
        else:
            self.head = tempy
        # same as prevy
        if prevy is not None:
            prevy.next = tempx
        else:
            self.head = tempx
        # swap next pointers
        tempy.next, tempx.next = tempx.next, tempy.next

how it works

llist = LinkedList()
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print('origin')
llist.printList()
llist.swapnode(1, 3)
print('new')
llist.printList()
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
origin
1
2
3
4
5
new
3
2
1
4
5

Know More About Time Complexity
Time Complexity — Big O Notation

REFERENCE
https://www.geeksforgeeks.org/sort-elements-by-frequency/
https://www.geeksforgeeks.org/linked-list-vs-array/
https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
https://www.geeksforgeeks.org/swap-nodes-in-a-linked-list-without-swapping-data/