Linked lists

Download exercises zip

Browse files online

0 Introduction

In these exercises, you will be implementing several versions of a LinkedList, improving its performances with each new version.

References

• Luca Bianco’s theory slides (Monodirectional list)

• LinkedList Abstract Data Type on the book

• Implementing LinkedListLinkedLists on the book

NOTE: What the book calls UnorderedList, in this lab is just called LinkedList. May look confusing, but in the wild you will never find code called UnorderedList so let’s get rid of the weird name right now!

What to do

• unzip exercises in a folder, you should get something like this:

linked-lists
    linked-lists.ipynb
    linked_list_test.py
    linked_list.py
    linked_list_sol.py
    linked_list_v2_sol.py
    linked_list_v2_test_sol.py
    linked_list_v3_sol.py
    linked_list_v3_test_sol.py
    jupman.py
    sciprog.py

• open the editor of your choice (for example Visual Studio Code, Spyder or PyCharme), you will edit the files ending in .py files

• Go on reading this notebook, and follow instuctions inside.

0.1 Initialization

A LinkedList for us is a linked list starting with a pointer called head that points to the first Node (if the list is empty the pointer points to None). Think of the list as a chain where each Node can contain some data retriavable with Node.get_data() method and you can access one Node at a time by calling the method Node.get_next() on each node.

Let’s see how a LinkedList should behave:

from linked_list_sol import *

ll = LinkedList()

At the beginning the LinkedList is empty:

print(ll)

LinkedList:

NOTE: print calls __str__ method, which in our implementation was overridden to produce a nice string you’ve just seen. Still, we did not override __repr__ method which is the default one used by Jupyter when displaying on object without using print, so if you omit it you won’t get nice display:

ll

<linked_list_sol.LinkedList at 0x7fc27bd69250>

0.2 Growing

Main way to grow a LinkedList is by using the .add method, which executes in costant time \(O(1)\):

ll.add('a')

Internally, each time you call .add a new Node object is created which will hold the actual data that you are passing. In this implementation, users of the class are supposed to never get instances of Node, they will just be able to see the actual data contained in the Nodes:

print(ll)

LinkedList: a

Notice that .add actually inserts nodes at the beginning :

ll.add('b')

print(ll)

LinkedList: b,a

ll.add('c')

print(ll)

LinkedList: c,b,a

Our basic LinkedList instance will only hold a pointer to the first Node of the chain (such pointer is called _next). When you add an element:

1. a new Node is created

2. provided data is stored inside new node

3. the new node _next field is set to point to current first Node

4. the new node becomes the first node of the LinkedList, by setting LinkedList._next to new node

0.3 Visiting

Any method that needs to visit the LinkedList will have to start from the first Node pointed by LinkedList._next and then follow the chain of _next links from one Node to the next one. This is why the data structure is called ‘linked’. While insertion at the beginning is very fast, retrieving an element at arbitrary position requires a linear scan which in worst case costs \(O(n)\).

1 v1: a slow LinkedList

Implement the missing methods in linked_list.py, in the order they are presented in the skeleton. Before implementing, read carefully all this point 1) and all its subsections (1.a,b and c)

1.a) Testing

You will have two files to look at, the code in linked_list.py and the test code in a separate linked_list_test.py file:

• linked_list.py

• linked_list_test.py

You can run tests with this shell command:

python3 -m unittest linked_list_test

Let’s look inside the first lines of linked_list_test.py code, you will see a structure like this:

from linked_list import *
import unittest

class LinkedListTest(unittest.TestCase):

    def myAssert(self, linked_list, python_list):
        #####  etc #####


class AddTest(LinkedListTest):

    def test_01_init(self):
        #####  etc #####

    def test_04_add(self):
        #####  etc #####

class SizeTest(LinkedListTest):
    #####  etc  #####

Note:

• the test automatically imports everything from first module linked_list, so when you run the test, it automatically loads the file you will be working on.) :

from linked_list import *

• there is a base class for testing called LinkedListTest

• there are many classes for testing individual methods, each class inherits from LinkedListTest

• You will be writing several versions of the linked list. For the first one, you won’t need myAssert

• This time there is not much Python code to find around, you should rely solely on theory from the slides and book, method definitions and your intuition

1.b) Differences with the book

• We don’t assume the list has all different values

• We used more pythonic names for properties and methods, so for example private attribute Node.data was renamed to Node._data and accessor method Node.getData() was renamed to Node.get_data(). There are nicer ways to handle these kind of getters/setters pairs called ‘properties’ but we won’t address them here.

• In boundary cases like removing a non-existing element we prefer to raise an LookupError with the command

raise LookupError("Some error occurred!")

In general, this is the behaviour you also find in regular Python lists.

1.c) Please remember…

WARNING: Methods of the class LinkedList are never supposed to return instances of Node.

If you see them returned in the tests, then you are making some mistake. Users of LinkedList are should only be able to get access to items inside the Node data fields.

WARNING: Do not use a Python list to hold data inside the data structure

Differently from the CappedStack exercise, here you can only use Node class. Each Node in the _data field can hold only one element which is provided by the user of the class, and we don’t care about the type of the value the user gives us (so it can be an int, a float, a string, or even a Python list !)

VII COMMANDMENT: You shall also draw lists on paper

Helps a lot avoiding mistakes!

VIII COMMANDMENT You shall never ever reassing self !

Never write horrors such as this:

class LinkedList:
    def my_method(self):
        self = {'my_field':666}    # SIN

VI COMMANDMENT: You shall use return command only if you see written RETURN in function description!

If there is no return in the description, it is intended to return None. In this case you don’t even need to write return None, as Python will do it implicitly for you.

2 v2 faster size

2.1 Save a copy of your work

You already wrote a lot of code, and you don’t want to lose it, right? Since we are going to make many modifications, when you reach a point when the code does something useful, it is good practice to save a copy of what you have done somewhere, so if you later screw up something, you can always restore the copy.

• Copy the whole folder linked-lists in a new folder linked-lists-v1

• Add also in the copied folder a separate README.txt file, writing inside the version (like 1.0), the date, and a description of the main features you implemented (for example “Simple linked list, not particularly performant”).

• Backing up the work is a form of the so-called versioning : there are much better ways to do it (like using git) but we don’t address them here.

WARNING: DO NOT SKIP THIS STEP!

No matter how smart you are, you will fail, and a backup may be the only way out.

WARNING: HAVE YOU READ WHAT I JUST WROTE ????

Just. Copy. The. Folder.

2.2. Improve size

Once you saved your precious work in the copy folder linked-lists-v1, you can now more freely improve the current folder linked-lists, being sure your previous efforts are not going to get lost!

As a first step, in linked-lists/linked_list.py implement a size() method that works in O(1). To make this work without going through the whole list each time, we will need a new _size field that keeps track of the size. When the list is mutated with methods like add, append, etc you will also need to update the _size field accordingly. Proceed like this:

2.2.1) add a new field _size in the class constructor and initialize it to zero

2.2.2) modify the size() method to just return the _size field.

2.2.3) The data structure starts to be complex, and we need better testing. If you look at the tests, very often there are lines of code like self.assertEquals(to_py(ul), ['a', 'b']) in the test_add method:

def test_add(self):
    ul = LinkedList()
    self.myAssert(ul, [])
    ul.add('b')
    self.assertEquals(to_py(ul), ['b'])
    ul.add('a')
    self.assertEquals(to_py(ul), ['a', 'b'])

Last line checks our linked list ul contains a sequence of linked nodes that once transformed to a python list actually equals ['a', 'b']. Since in the new implementation we are going to mutate _size field a lot, it could be smart to also check that ul.size() equals len(["a", "b"]). Repeating this check in every test method could be quite verbose. Instead, we can do a smarter thing, and develop in the LinkedListTest class a new assertion method on our own:

If you noticed, there is a method myAssert in LinkedListTest class (in the current linked-lists/linked_list_test.py file) which we never used so far, which performs a more thourough check:

class LinkedListTest(unittest.TestCase):

    def myAssert(self, linked_list, python_list):
        """ Checks provided linked_list can be represented as the given python_list. Since v2.
        """
        self.assertEquals(to_py(linked_list), python_list)
        # check this new invariant about the size
        self.assertEquals(linked_list.size(), len(python_list))

WARNING: method myAssert must not start with test, otherwise unittest will run it as a test!

2.3.4) Now, how to use this powerful new myAssert method? In the test class, just replace every occurence of

self.assertEquals(to_py(ul), ['a', 'b'])

into calls like this:

self.myAssert(ul, ['a', 'b'])

WARNING: Notice the to_py(  ) enclosing ul is gone.

2.3.5) Actually update _size in the various methods where data is mutated, like add, insert, etc.

2.3.6) Run the tests and hope for the best ;-)

python3 -m unittest linked_list_test

3 v3 Faster append

We are now better equipped to make further improvements. Once you’re done implementing the above and made sure everything works, you can implement an append method that works in \(O(1)\) by adding an additional pointer in the data structure that always point at the last node. To further exploit the pointer, you can also add a fast last(self) method that returns the last value in the list. Proceed like this:

3.1 Save a copy of your work

• Copy the whole folder linked-lists in a new folder linked-lists-v2

• Add also in the copied folder a separate README.txt file, writing inside the version (like 2.0), the date, and a description of the main features you implemented (for example “Simple linked list, not particularly performant”).

WARNING: DO NOT SKIP THIS STEP!

3.2 add _last field

Work on linked_list.py and simply add an additional pointer called _last in the constructor.

3.3 add method skeleton

Copy this method last into the class. Just copy it, don’t implement it for now.

def last(self):
    """ Returns the last element in the list, in O(1).

        - If list is empty, raises a ValueError. Since v3.
    """
    raise ValueError("TODO implement me!")

3.4 test driven development

Let’s do some so-called test driven development, that is, first we write the tests, then we write the implementation.

WARNING: During the exam you may be asked to write tests, so don’t skip writing them now !!

3.4.1 LastTest

Create a class LastTest which inherits from LinkedListTest, and add this method Implement a test for last() method, by adding this to LinkedListTest class:

def test_01_last(self):
    raise Exception("TODO IMPLEMENT ME !")

In the method, create a list and add elements using only calls to add method and checks using the myAssert method. When done, ask your instructor if the test is correct (or look at the proposed solution), it is important you get it right otherwise you won’t be able to properly test your code.

3.4.2 improve myAssert

You already have a test for the append() method, but, how can you be sure the _last pointer is updated correctly throughout the code? When you implemented the fast size() method you wrote some invariant in the myAssert method. We can do the same this time, too. Find the invariant and add the corresponding check to the myAssert method. When done, ask your instructor if the invariant is correct (or look at the proposed solution): it is important you get it right otherwise you won’t be able to properly test your code.

3.5 update methods that mutate the LinkedList

Update the methods that mutate the data structure (add, insert, remove …) so they keep _last pointed to last element. If the list is empty, _last will point to None. Take particular care of corner cases such as empty list and one element list.

3.6 Run tests

Cross your fingers and run the tests!

python3 -m unittest linked_list_test

4 v4 Go bidirectional

Our list so far has links that allow us to traverse it fast in one direction. But what if we want fast traversal in the reverse direction, from last to first element? What if we want a pop() that works in \(O(1)\) ? To speed up these operations we could add backward links to each Node. Note no solution is provided for this part (yet).

Proceed in the following way:

4.1 Save your work

Once you’re done with previous points, save the version you have in a folder linked-list-v3 somewhere adding in the README.txt comments about the improvements done so far, the version number (like 3.0) and the date. Then start working on a new copy.

4.2 Node backlinks

In Node class, add backlinks by adding the attribute _prev and methods get_prev(self) and set_prev(self, pointer).

4.3 Better str

Improve __str__ method so it shows presence or absence of links, along with the size of the list (note you might need to adapt the test for str method):

• next pointers presence must be represented with > character , absence with * character. They must be put after the item representation.

• prev pointers presence must be represented with < character , absence with * character. They must be put befor the item representation.

For example, for the list ['a','b','c'], you would have the following representation:

LinkedList(size=3):*a><b><c*

As a special case for empty list you should print the following:

LinkedList(size=0):**

Other examples of proper lists, with 3, 2, and 1 element can be:

LinkedList(size=3):*a><b><c*
LinkedList(size=2):*a><b*
LinkedList(size=1):*a*

This new __str__ method should help you to spot broken lists like the following, were some pointers are not correct:

Broken list, all prev pointers are missing:
LinkedList(size=3):*a>*b>*c*

Broken list, size = 3 but shows only one element with next pointer set to None:
LinkedList(size=3):*a*

Broken list, first backward pointer points to something other than None
LinkedList(size=3):<a>*b><c*

4.4 Modify add

Update the LinkedList add method to take into account you now have backlinks. Take particular care for the boundary cases when the list is empty, has one element, or for nodes at the head and at the tail of the list.

4.5 Add to_python_reversed

Implement to_python_reversed method with a linear scan by using the newly added backlinks:

def to_python_reversed(self):
    """ Returns a regular Python list with the elements in reverse order,
        from last to first. Since v3. """
    raise Exception("TODO implement me")

Add also this test, and make sure it pass:

def test_to_python_reversed(self):
    ul = LinkedList()
    ul.add('c')
    ul.add('b')
    ul.add('a')
    pr = to_py(ul)
    pr.reverse()  # we are reversing pr with Python's 'reverse()' method
    self.assertEquals(pr, ul.to_python_reversed())

4.6 Add invariant

By using the method to_python_reversed(), add a new invariant to the myAssert method. If implemented correctly, this will surely spot a lot of possible errors in the code.

4.7 Modify other methods

Modify all other methods that mutate the data structure (insert, remove, etc) so that they update the backward links properly.

4.8 Run the tests

If you wrote meaningful tests and all pass, congrats!

5 EqList

Open file eqlist.py , which is a simple linked list, and start editing the following methods.

5.1 eq

Implement the method __eq__ (with TWO underscores before and TWO underscores after ‘eq’) !:

def __eq__(self, other):
    """ Returns True if self is equal to other, that is, if all the data elements in the respective
        nodes are the same. Otherwise, return False.

        NOTE: compares the *data* in the nodes, NOT the nodes themselves !
    """

Testing: python -m unittest eqlist_test.EqTest

5.2 remsub

Implement the method remsub:

def remsub(self, rem):
    """ Removes the first elements found in this LinkedList that match subsequence rem
        Parameter rem is the subsequence to eliminate, which is also a LinkedList.

        Examples:
            aabca  remsub ac  =  aba
            aabca  remsub cxa =  aaba  # when we find a never matching character in rem like 'x' here,
                                         the rest of rem after 'x' is not considered.
            aabca  remsub ba  =  aac
            aabca  remsub a   =  abca
            abcbab remsub bb  =  acab
    """

Testing: python3 -m unittest eqlist_test.RemsubTest

6 Cloning

Start editing the file cloning.py, which contains a simplified LinkedList.

6.1 rev

Implement the method rev(self) that you find in the skeleton and check provided tests pass.

Testing: python3 -m unittest cloning_test.RevTest

def rev(self):
    """ Returns a *new* LinkedList, which is the reversed version of this one.
        Function must run in O(n), and try to make this function as fast as possible,
        without using python lists or extra fields.
    """

from cloning_sol import *

lla = LinkedList()
lla.add('c')
lla.add('b')
lla.add('a')
print(lla)

LinkedList: a,b,c

llb = lla.rev()

print(llb)

LinkedList: c,b,a

print(lla)

LinkedList: a,b,c

6.2 clone

Implement the method clone(self) that you find in the skeleton and check provided tests pass.

def clone(self):
    """ Return a *copy* of this LinkedList in O(n)
        NOTE: since we are making a copy, the output of this function
        won't contain any Node instance from the original list. Still, new Node
        instances will point to the same data items of the original list
    """

Testing: python3 -m unittest cloning_test.CloneTest

Example (for more examples look at the tests):

orig = LinkedList()
orig.add('c')
orig.add('b')
orig.add('a')
print(orig)

LinkedList: a,b,c

cp = orig.clone()
print(cp)

LinkedList: a,b,c

cp.remove('b')

print(cp)

LinkedList: a,c

print(orig)

LinkedList: a,b,c

6.3 Slice

Implement the method slice:

def slice(self, start, end):
    """ RETURN a NEW LinkedList created by copying nodes of this list
        from index start INCLUDED to index end EXCLUDED

        - if start is greater or equal than end, returns an empty LinkedList
        - if start is greater than available nodes, returns an empty LinkedList
        - if end is greater than the available nodes, copies all items until the tail without errors
        - if start index is negative, raises ValueError
        - if end index is negative, raises ValueError

        - IMPORTANT: All nodes in the returned LinkedList MUST be NEW
        - DO *NOT* modify original linked list
        - DO *NOT* add an extra size field
        - MUST execute in O(n), where n is the size of the list

    """

Testing: python3 -m unittest cloning_test.SliceTest

Example:

from cloning_sol import *

la = LinkedList()
la.add('g')
la.add('f')
la.add('e')
la.add('d')
la.add('c')
la.add('b')
la.add('a')

print(la)

LinkedList: a,b,c,d,e,f,g

Creates a NEW LinkedList copying nodes from index 2 INCLUDED up to index 5 EXCLUDED:

lb = la.slice(2,5)

print(lb)

LinkedList: c,d,e

Note original LinkedList is still intact:

print(la)

LinkedList: a,b,c,d,e,f,g

Special cases

If start is greater or equal then end, you get an empty LinkedList:

print(la.slice(5,3))

LinkedList:

If start is greater than available nodes, you get an empty LinkedList:

print(la.slice(10,15))

LinkedList:

If end is greater than the available nodes, you get a copy of all the nodes until the tail without errors:

print(la.slice(3,10))

LinkedList: d,e,f,g

Using negative indexes for either start , end or both raises ValueError:

la.slice(-3,4)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-184-e3380bb66e77> in <module>()
----> 1 la.slice(-3,4)

~/Da/prj/sciprog-ds/prj/exams/2020-06-16/linked_list_sol.py in slice(self, start, end)
     63
     64         if start < 0:
---> 65             raise ValueError('Negative values for start are not supported! %s ' % start)
     66         if end < 0:
     67             raise ValueError('Negative values for end are not supported: %s' % end)

ValueError: Negative values for start are not supported! -3

la.slice(1,-2)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-185-8e09ec468c30> in <module>()
----> 1 la.slice(1,-2)

~/Da/prj/sciprog-ds/prj/exams/2020-06-16/linked_list_sol.py in slice(self, start, end)
     65             raise ValueError('Negative values for start are not supported! %s ' % start)
     66         if end < 0:
---> 67             raise ValueError('Negative values for end are not supported: %s' % end)
     68
     69         ret = LinkedList()

ValueError: Negative values for end are not supported: -2

7 More exercises

Start editing the file more.py, which contains a simplified LinkedList.

7.1 occurrences

Implement this method:

def occurrences(self, item):
    """
        Returns the number of occurrences of item in the list.

        - MUST execute in O(n) where 'n' is the length of the list.
    """

Testing: python3 -m unittest more_test.OccurrencesTest

**Examples: **

from more_sol import *

ul = LinkedList()
ul.add('a')
ul.add('c')
ul.add('b')
ul.add('a')
print(ul)

LinkedList: a,b,c,a

print(ul.occurrences('a'))

2

print(ul.occurrences('c'))

1

print(ul.occurrences('z'))

0

7.2 shrink

Implement this method in LinkedList class:

def shrink(self):
    """
        Removes from this LinkedList all nodes at odd indeces (1, 3, 5, ...),
        supposing that the first node has index zero, the second node
        has index one, and so on.

        So if the LinkedList is
            'a','b','c','d','e'
        a call to shrink will transform the LinkedList into
            'a','c','e'

        - MUST execute in O(n) where 'n' is the length of the list.
        - Does *not* return anything.
    """
    raise Exception("TODO IMPLEMENT ME!")

Testing: python3 -m unittest more_test.ShrinkTest

ul = LinkedList()
ul.add('e')
ul.add('d')
ul.add('c')
ul.add('b')
ul.add('a')
print(ul)

LinkedList: a,b,c,d,e

ul.shrink()
print(ul)

LinkedList: a,c,e

7.3 dup_first

Implement the method dup_first:

def dup_first(self):
    """ MODIFIES this list by adding a duplicate of first node right after it.

        For example, the list 'a','b','c' should become 'a','a','b','c'.
        An empty list remains unmodified.

        - DOES NOT RETURN ANYTHING !!!

    """

    raise Exception("TODO IMPLEMENT ME !")

Testing: python3 -m unittest more_test.DupFirstTest

7.4 dup_all

Implement the method dup_all:

def dup_all(self):
    """ Modifies this list by adding a duplicate of each node right after it.

        For example, the list 'a','b','c' should become 'a','a','b','b','c','c'.
        An empty list remains unmodified.

        - MUST PERFORM IN O(n) WHERE n is the length of the list.

        - DOES NOT RETURN ANYTHING !!!
    """

    raise Exception("TODO IMPLEMENT ME !")

Testing: python3 -m unittest more_test.DupAllTest

7.5 mirror

Implement following mirror function. NOTE: the function is external to class LinkedList.

def mirror(lst):
    """ Returns a new LinkedList having double the nodes of provided lst
        First nodes will have same elements of lst, following nodes will
        have the same elements but in reversed order.

        For example:

            >>> mirror(['a'])
            LinkedList: a,a

            >>> mirror(['a','b'])
            LinkedList: a,b,b,a

            >>> mirror(['a','c','b'])
            LinkedList: a,c,b,b,c,a

    """
    raise Exception("TODO IMPLEMENT ME !")

Testing: python -m unittest more_test.MirrorTest

7.6 norep

Implement the method norep:

def norep(self):
    """ MODIFIES this list by removing all the consecutive
        repetitions from it.

        - MUST perform in O(n), where n is the list size.
    """

Testing: python3 -m unittest more_test.NorepTest

Example:

ll = LinkedList()
ll.add('e')
ll.add('c')
ll.add('c')
ll.add('c')
ll.add('d')
ll.add('d')
ll.add('b')
ll.add('a')
ll.add('a')
ll.add('c')
ll.add('c')
ll.add('a')
ll.add('a')
ll.add('a')

print(ll)

LinkedList: a,a,a,c,c,a,a,b,d,d,c,c,c,e

ll.norep()

print(ll)

LinkedList: a,c,a,b,d,c,e

7.7 find_couple

Implement following find_couple method.

def find_couple(self, a, b):
    """ Search the list for the first two consecutive elements having data equal to
        provided a and b, respectively. If such elements are found, the position
        of the first one is returned, otherwise raises LookupError.

        - MUST run in O(n), where n is the size of the list.
        - Returned index start from 0 included
    """

Testing: python3 -m unittest more_test.FindCoupleTest

7.8 swap

Implement the method swap:

def swap(self, i, j):
    """ Swap the data of nodes at index i and j. Indeces start from 0 included.
        If any of the indeces is out of bounds, rises IndexError.

        NOTE: You MUST implement this function with a single scan of the list.
    """

Testing: python3 -m unittest more_test.SwapTest

7.9 gaps

Given a linked list of size n which only contains integers, a gap is an index i, 0<i<n, such that L[i−1]<L[i]. For the purpose of this exercise, we assume an empy list or a list with one element have zero gaps

Example:

 data:  9 7 6 8 9 2 2 5
index:  0 1 2 3 4 5 6 7

contains three gaps [3,4,7] because:

• number 8 at index 3 is greater than previous number 6 at index 2

• number 9 at index 4 is greater than previous number 8 at index 3

• number 5 at index 7 is greater than previous number 2 at index 6

Implement this method:

def gaps(self):
    """ Assuming all the data in the linked list is made by numbers,
        finds the gaps in the LinkedList and return them as a Python list.

        - we assume empty list and list of one element have zero gaps
        - MUST perform in O(n) where n is the length of the list

        NOTE: gaps to return are *indeces* , *not* data!!!!
    """

Testing: python3 -m unittest more_test.GapsTest

7.10 flatv

Suppose a LinkedList only contains integer numbers, say 3,8,8,7,5,8,6,3,9. Implement method flatv which scans the list: when it finds the first occurence of a node which contains a number which is less then the previous one, and the less than successive one, it inserts after the current one another node with the same data as the current one, and exits.

Example:

for Linked list 3,8,8,7,5,8,6,3,9

calling flatv should modify the linked list so that it becomes

Linked list 3,8,8,7,5,5,8,6,3,9

Note that it only modifies the first occurrence found 7,5,8 to 7,5,5,8 and the successive sequence 6,3,9 is not altered

Implement this method:

def flatv(self):

Testing: python3 -m unittest more_test.FlatvTest

7.11 bubble_sort

You will implement bubble sort on a LinkedList.

def bubble_sort(self):
    """ Sorts in-place this linked list using the method of bubble sort

        - MUST execute in O(n^2) where n is the length of the linked list
    """

As a reference, you can look at this example_bubble implementation below that operates on regular python lists. Basically, you will have to translate the for cycles into two suitable while and use node pointers.

NOTE: this version of the algorithm is inefficient as we do not use j in the inner loop: your linked list implementation can have this inefficiency as well.

Testing: python3 -m unittest more_test.BubbleSortTest

def example_bubble(plist):
    for j in range(len(plist)):
        for i in range(len(plist)):
            if i + 1 < len(plist) and plist[i]>plist[i+1]:
                temp = plist[i]
                plist[i] = plist[i+1]
                plist[i+1] = temp

my_list = [23, 34, 55, 32, 7777, 98, 3, 2, 1]
example_bubble(my_list)
print(my_list)

[1, 2, 3, 23, 32, 34, 55, 98, 7777]

7.12 merge

Implement this method:

def merge(self,l2):
    """ Assumes this linkedlist and l2 linkedlist contain integer numbers
        sorted in ASCENDING order, and  RETURN a NEW LinkedList with
        all the numbers from this and l2 sorted in DESCENDING order

        IMPORTANT 1: *MUST* EXECUTE IN O(n1+n2) TIME where n1 and n2 are
                     the sizes of this and l2 linked_list, respectively

        IMPORTANT 2: *DO NOT* attempt to convert linked lists to
                     python lists!
    """

Testing: python3 -m unittest more_test.MergeTest

7.13 couple_sort

Implement this method:

def couple_sort(self):
    """ MODIFIES the linked list by considering couples of nodes at even indexes
        and their successors: if a node data is lower than its successor data,
        swaps the nodes *data*.

        - ONLY swap *data*, DO NOT change node links.
        - if linked list has odd size, simply ignore the exceeding node.
        - MUST execute in O(n), where n is the size of the list
        - NOTE: we don't want to sort the whole list, just the single couples.
    """

Testing: python3 -m unittest more_test.CoupleSortTest

from more_sol import *
from more_test import to_ll

ll = to_ll([4,3,5,2,6,7,6,3,2,4,5,3,2])

print(ll)

LinkedList: 4,3,5,2,6,7,6,3,2,4,5,3,2

ll.couple_sort()

print(ll)

LinkedList: 3,4,2,5,6,7,3,6,2,4,3,5,2

Notice it sorted each couple at even positions. This particular linked list has odd size (13 items), so last item 2 was not considered.

7.14 linked algebra

Implement this method:

def linalg(self):
    """ Assume nodes hold data as a string "kc" where k is a single digit
        and c any character.

        MODIFY the linked list by stripping the k from original nodes,
        and inserting k-1 new nodes next to each node.

        - ASSUME every k is >= 1
        - MUST execute in O(s) where s is the sum of all k found.
    """

Testing: python3 -m unittest more_test.LinAlgTest

Example:

from more_sol import *

ll = LinkedList()

ll.add('2c')
ll.add('5b')
ll.add('3a')

print(ll)

LinkedList: 3a,5b,2c

ll.linalg()   # returns NOTHING!

print(ll)

LinkedList: a,a,a,b,b,b,b,b,c,c

with 3 nodes modified and 7 new nodes inserted

7.15 sepel

Implement this method:

def sepel(self, el):
    """ Separates this list into two lists:

        - this list will have all nodes without el as data
        - the other list will contain all nodes with el as data

        - IMPORTANT: DO *NOT* create new nodes, REUSE existing ones!!
        - MUST execute in O(n), where n is the length of the list
    """

Testing: python3 -m unittest more_test.SepelTest

Example:

from more_sol import *
la = LinkedList()
la.add('c')
la.add('e')
la.add('c')
la.add('d')
la.add('c')
la.add('c')
la.add('b')
la.add('a')
la.add('c')

print(la)

LinkedList: c,a,b,c,c,d,c,e,c

lb = la.sepel('c')

print(la)

LinkedList: a,b,d,e

print(lb)

LinkedList: c,c,c,c,c

7.16 linked pivot

Implement this method:

def pivot(self):
    """ Selects first node data as pivot, and then MOVES before the pivot
        all the nodes which have data value STRICTLY LESS (<) than the pivot.
        Finally, RETURN the number of moved nodes.

        IMPORTANT:
        - *DO NOT* create new nodes
        - nodes less than pivot must be in the reversed order they were found
        - nodes greater or equal than pivot will maintain the original order
        - MUST EXECUTE in O(n), where n is the list size
    """

Testing: python3 -m unittest more_test.PivotTest

Example:

from more_sol import *
from more_test import to_ll

ll = to_ll([7, 12, 1, 3, 8, 9, 6, 4, 7, 2, 10])

print(ll)

LinkedList: 7,12,1,3,8,9,6,4,7,2,10

res = ll.pivot()

res   # there were 5 elements strictly less than pivot 7

5

Note elements \(< 7\) are in reverse order in which they were found, elements \(\geq7\) are in the original order

print(ll)

LinkedList: 2,4,6,3,1,7,12,8,9,7,10

8 Last exercises

For these exercises, you also need to take care about attributes size and _last pointer.

8.1 rotate

✪✪ Now implement this method:

Remember to update also _last and _size attributes !!!

def rotate(self):
    """ Rotate the list of 1 element, that is, removes last node and
        inserts it as the first one.

       - MUST execute in O(n) where n is the length of the list
       - Remember to also update _last pointer
       - WARNING: DO *NOT* try to convert whole linked list to a python list
       - WARNING: DO *NOT* swap node data or create nodes, I want you to
                  change existing node links !!
    """

Testing: python3 -m unittest last_test.RotateTest

Example:

from last_sol import *

ll = LinkedList()
ll.add('d')
ll.add('c')
ll.add('b')
ll.add('a')
print(ll)

LinkedList: a,b,c,d

ll.rotate()

print(ll)

LinkedList: d,a,b,c

8.2 rotaten

✪✪✪ Implement this method:

def rotaten(self, k):
    """ Rotate k times the linkedlist

        - k can range from 0 to any positive integer number (even greater than list size)
        - if k < 0 raise ValueError

        - MUST execute in O( n-(k%n) ) where n is the length of the list
        - WARNING: DO *NOT* call .rotate() k times !!!!
        - WARNING: DO *NOT* try to convert whole linked list to a python list
        - WARNING: DO *NOT* swap node data or create nodes, I want you to
                   change node links !!
    """

Testing: python3 -m unittest last_test.RotatenTest

IMPORTANT HINT

The line “MUST execute in O( n-(k%n) ) where n is the length of the list” means that you have to calculate m = k%n, and then only scan first n-m nodes!

Example:

ll = LinkedList()
ll.add('h')
ll.add('g')
ll.add('f')
ll.add('e')
ll.add('d')
ll.add('c')
ll.add('b')
ll.add('a')
print(ll)

LinkedList: a,b,c,d,e,f,g,h

ll.rotaten(0)  # changes nothing

print(ll)

LinkedList: a,b,c,d,e,f,g,h

ll.rotaten(3)

print(ll)

LinkedList: f,g,h,a,b,c,d,e

ll.rotaten(8)  # changes nothing

print(ll)

LinkedList: f,g,h,a,b,c,d,e

ll.rotaten(5)

print(ll)

LinkedList: a,b,c,d,e,f,g,h

ll.rotaten(11)  # 11 = 8 + 3 , only rotates 3 nodes

print(ll)

LinkedList: f,g,h,a,b,c,d,e

IMPORTANT: MUST WORK WITH HUGE k

It should terminate real fast even with a humongous k, if you don’t implement it with the required complexity rest assured this will never print 'Finished!'

ll.rotaten(11**18)
print('Finished! Result is', ll)

Finished! Result is LinkedList: e,f,g,h,a,b,c,d

8.3 plus_one

Supposing the list can only hold digits from 0 to 9 as node data, implement this method:

def plus_one(self):
    """ MODIFIES the list by summing one to the integer number it represents
        - you are allowed to perform multiple scans of the linked list
        - remember the list has a _last pointer

        - MUST execute in O(N) where N is the size of the list
        - DO *NOT* create new nodes EXCEPT for special cases:
            a. empty list ( [] -> [5] )
            b. all nines ( [9,9,9] -> [1,0,0,0] )
        - DO *NOT* convert the digi list to a python int
        - DO *NOT* convert the digi list to a python list
        - DO *NOT* reverse the digi list
    """

Test: python3 -m unittest last_test.PlusOneTest

Example:

from last_sol import *

dl = LinkedList()

dl.add(9)
dl.add(9)
dl.add(7)
dl.add(3)
dl.add(9)
dl.add(2)

print(dl)

LinkedList: 2,9,3,7,9,9

dl.last()

9

dl.plus_one()

print(dl)

LinkedList: 2,9,3,8,0,0

Challenge

Ready for the challanges? Go on with Challenge worksheet