linked list

Implement a simple linked list with following basic operations

print
push
pop
append



In [1]:

    
class Node:
    def __init__(self, value: int):
#         print('push elem', value)
        self.value = value
        self.next = None
        
    def __repr__(self):
        is_next = False
        if self.next:
            is_next = True
#             return '<Node val(%s) know(%s)>' % (self.value, id(self.next))
            return '<Node val(%s) know(%s)>' % (self.value, self.next.value)
        return '<Node val(%s)>' % (self.value)
    
    def copy(self):
        return Node(self.value)



In [12]:

    
class LinkedList:
    def __init__(self):
        self.head = None
        
    def push(self, value: int):
        "Put new value in the first"
        tmp = Node(value)
        if not self.head:
            self.head = tmp
        else:
            tmp.next = self.head
            self.head = tmp

    def pop(self):
        "Give the first value out"
        if self.head:
            tmp = self.head.value
            self.head = self.head.next
            return tmp
        
    def append(self, value):
        "Put the new value in the last"
        tmp = Node(value)
        if not self.head:
            self.head = tmp
        else:
            last = self.head
            while last.next:
                last = last.next
            last.next = tmp
        
    def first(self):
        "give the first value in the list"
        pass
        
    def last(self):
        "give the first value in the list"
        pass
    
    def print(self):
        tmp = self.head
        ct = 0
        print('=' * 8)
        while tmp:
            print(' ', tmp.value)
            ct += 1
            tmp = tmp.next
        print('=' * 8, 'tot elems', ct)
        
    def delete(self, value):
        first = self.head
        if first and first.value == value:
            self.head = self.head.next
            print('deleted !', value)
            return
        while first.next:
            if first.next.value == value:
                first.next = first.next.next
                print('deleted !', value)
                return
            first = first.next
            
    def position(self, pos, d=False):
        tmp = self.head
        ct = 0
        while tmp:
            if ct == pos:
                return tmp.value
            ct += 1
            tmp = tmp.next
            
    def del_position(self, pos):
        tmp = self.head
        ct = 0
        if pos == 0:
            self.head = self.head.next
        
        print('\t')
        while tmp.next:
            ct += 1
            if ct == pos:
                print('\t->', tmp.next.value)
                tmp.next = tmp.next.next
                return



In [13]:

    
ll = LinkedList()
ll.push(12)
ll.push(11)
ll.push(10)

ll.print()

assert ll.position(1) == 11
assert ll.position(0) == 10
assert ll.position(2) == 12
assert ll.position(3) == None









    



========
  10
  11
  12
======== tot elems 3



In [14]:

    
ll.append(13)
assert ll.position(3) == 13
ll.position(3)









    Out[14]:





13



In [15]:

    
ll = LinkedList()

ll.append(12)
ll.append(13)
ll.append(14)
ll.append(15)
ll.append(16)
ll.append(17)

ll.print()









    



========
  12
  13
  14
  15
  16
  17
======== tot elems 6



In [16]:

    
ll.del_position(4)



In [17]:

    
ll.print()
assert ll.position(1) == 14









    



========
  12
  14
  15
  16
  17
======== tot elems 5



In [18]:

    
ll.delete(12)

ll.print()









    



deleted ! 12
========
  14
  15
  16
  17
======== tot elems 4



In [19]:

    
ll.delete(14)

assert ll.position(0) == 15

ll.print()









    



deleted ! 14
========
  15
  16
  17
======== tot elems 3



In [20]:

    
ll.delete(17)

ll.print()









    



deleted ! 17
========
  15
  16
======== tot elems 2

Linked List

Swap adjuscent elements with 1 unit gaps. like swap 1,2 and 3,4 and 5, 6 and so,..

* Inputs: 1, 2,     3, 4,    5, 6, ...
* Exp. Output: 2, 1,     4, 3,    6, 5, ...



In [21]:

    
class NewLinkedList(LinkedList):
    def custom_swap_values(self):
        first = self.head
        second = self.head.next
        while first and second:
            first.value, second.value  = second.value, first.value
            try:
                first = first.next.next
                second = second.next.next
            except AttributeError:
                break

    def custom_swap_nodes(self):
        if not (self.head and self.head.next):
            return
        # adding a temp node.
        temp_node = Node(-1)
        temp_node.next = self.head
        self.head = temp_node
        # zero -> first -> second -> third
        zero_node = temp_node # just created
        
        ct = 0
        
        while zero_node.next and zero_node.next.next:
            if ct < 5:
                ct += 1
            else:
                break
            # zero -> first -> second -> third
            first_node = zero_node.next # required
            second_node = zero_node.next.next # required
            third_node = zero_node.next.next.next # can be null
            # print(zero_node, first_node, second_node, third_node)
            # zero -> second
            zero_node.next = second_node
            second_node.next = first_node
            first_node.next = third_node
            # next iteration
            zero_node = zero_node.next.next
        
        self.head = self.head.next



In [22]:

    
ll = NewLinkedList()

for i in range(1, 9):
    ll.append(i)

ll.print()
ll.custom_swap_nodes()
# print('--' * 5)
ll.print()









    



========
  1
  2
  3
  4
  5
  6
  7
  8
======== tot elems 8
========
  2
  1
  4
  3
  6
  5
  8
  7
======== tot elems 8

MergeSort Linked List



In [23]:

    
ll = LinkedList()

ll.append(5)
ll.append(4)
ll.append(3)
ll.append(2)
ll.append(1)
# ll.append(11)
# ll.append(12)
# ll.append(14)
# ll.append(15)
ll.print()









    



========
  5
  4
  3
  2
  1
======== tot elems 5



In [25]:

    
def ll_merge_sort(head_node):
    print('---' * 5)
    ct = 0
    node1 = head_node

    # check length
    while node1:
        ct += 1
        node1 = node1.next
    
    # single node ll is always sorted by itself
    if ct < 2:
        return head_node

    # splitting nodes if more nodes are there
    node1 = head_node
    tmp = head_node
    for i in range(ct -1):
        tmp = tmp.next
    node2 = tmp.next
    tmp.next = None

    # sorting
    new_nodes = None
    while node1 or node2:
        if node1.value > node2.value:
            if not new_nodes:
                new_nodes = node1
                tmp = new_nodes
            else:
                tmp.next = node1
                node1 = node1.next
        else:
            if not new_nodes:
                new_nodes = node2
                tmp = new_nodes
            else:
                tmp.next = node2
                node2 = node2.next
                
    if node1 == None:
        node1 = node2
    
    tmp.next = node1
    
    return new_nodes



In [26]:

    
ll.print()









    



========
  5
  4
  3
  2
  1
======== tot elems 5



In [31]:

    
ll.print()









    



========
  5
  4
  3
  2
  1
======== tot elems 5

tips

learn to put things to paper



In [33]:

    
def merge_sort(mylist):
    l = len(mylist)
    if l <= 1:
        return mylist
    l1 = merge_sort(mylist[:int(l/2)])
    l2 = merge_sort(mylist[int(l/2):])
    new_list = []
    while l1 and l2:
        if l1[0] > l2[0]:
            new_list.append(l1[0])
            del l1[0]
        else:
            new_list.append(l2[0])
            del l2[0]
    if len(l1) == 0:
        l1 = l2
        del l2
    while l1:
        new_list.append(l1[0])
        del l1[0]
    return new_list

mylist = [4, 1, 2, 3]
print(mylist, "\t\t\t\t-->", merge_sort(mylist))
mylist = [4, 6, 7, 2, 9, 1, 2, 3]
print(mylist, "\t\t-->", merge_sort(mylist))
del mylist









    



[4, 1, 2, 3] 				--> [4, 3, 2, 1]
[4, 6, 7, 2, 9, 1, 2, 3] 		--> [9, 7, 6, 4, 3, 2, 2, 1]



In [35]:

    
ll = LinkedList()

ll.append(2)
ll.append(5)
ll.append(3)
ll.append(4)
ll.append(1)

ll.print()









    



========
  2
  5
  3
  4
  1
======== tot elems 5



In [ ]:



In [ ]:



In [ ]: