#=======================================================================
# Author: Isai Damier
# Title: Singly Linked List
# Project: geekviewpoint
# Package: datastructure
#
# Description: A LinkedList is a data structure that allows access
# to a collection of data using pointers/references. While an
# array can also be defined as above, LinkedLists and arrays differ
# in how they are stored in memory and in the operations they
# allow. Unlike an array that must be stored in a block of memory,
# the nodes of a LinkedList can be stored anywhere because each
# node has a reference to the node that succeeds it. Because the
# nodes are stored so loosely, inserting nodes into a LinkedList
# is easy; whereas in an array, all the succeeding elements must
# be shifted. Of course, insertion also means changing the size of
# the array, which means creating the entire array anew.
#
# Perhaps the greatest beauty of LinkedList is that it allows
# accessing an entire sequence of nodes using only one variable:
# a reference to the first node in the sequence.
#
# Countless operations can be performed on LinkedLists. Following
# are a few, ranging from the common to the very interesting.
#=======================================================================
#=====================================================================
# Time Complexity of Solution:
# O(n).
#
# Description: Given an array of sorted link lists, merge all
# the lists and return one large sorted list.
#
# Technical Details: Personally, I think of the process for
# merging two sorted arrays and apply it to n sorted LinkedList.
# The idea is to continuously find the mininum available
# node and add it to the result LinkedList. This same technique
# can be applied to sorting very large files in external drives.
#
# If a programmer does not want the duplicates, simply replace
# result.addToTail(currMin.data)
# with
# if(result.tail.data != currMin.data){
# result.addToTail(currMin.data)
# }
#=====================================================================
import collections
class SinglyLinkedList( object ):
def __init__( self ):
self.head , self.tail = None, None
@classmethod
def mergeSortedLL( self, lists ):
tracker = [None] * len( lists )
for i in range( len( lists ) ):
tracker[i] = lists[i].head
result = SinglyLinkedList()
currMin = self.getNextMin( lists, tracker )
while None != currMin:
result.addToTail( currMin.data )
currMin = self.getNextMin( lists, tracker )
return result
@classmethod
def getNextMin( self, lists, tracker ):
ndx = 0
while ndx < len( tracker ) and None == tracker[ndx]:
ndx += 1
if ndx >= len( tracker ) or None == tracker[ndx]:
return None
min_value = tracker[ndx]
for i in range( ndx + 1, len( lists ) ):
if None != tracker[i] and tracker[i].data < min_value.data:
min_value = tracker[i]
ndx = i
if None != min_value:
tracker[ndx] = tracker[ndx].next
return min_value
class Node( object ):
def __init__( self, data, next = None ):
self.data = data
self.next = next
import unittest
from algorithms.SinglyLinkedList import SinglyLinkedList
import random
class Test( unittest.TestCase ):
#=====================================================================
# Test of mergeSortedLL method, of class SinglyLinkedList.
#=====================================================================
def testMergeSortedLL( self ):
all_lists = [SinglyLinkedList()] * 9
for i in range( len( all_lists ) ):
size = random.randrange( len( all_lists ) )
tmp = SinglyLinkedList()
for x in range( size ):
tmp.addToTail( random.randrange( 25 ) )
tmp.sort()
all_lists[i] = tmp
# expected
expected = []
for l in all_lists:
for i in l.toArray():
expected.append( i )
expected.sort()
all_listsSize = 0
for l in all_lists:
all_listsSize += l.size()
self.assertEquals( all_listsSize, len( expected ) )
result = SinglyLinkedList.mergeSortedLL( all_lists )
for i in range( len( expected ) ):
self.assertEquals( expected[i], result.deleteFromHead().data )