Writing an algorithm to shift a linked list according to `k` variance

enoren5 · July 25, 2024, 3:46am

Write a function that takes in the head of a Singly Linked List and an integer k, shifts the list in place (i.e., doesn’t create a brand new list) by k positions, and returns its new head.
Shifting a Linked List means moving its nodes forward or backward and wrapping them around the list where appropriate. For example, shifting a Linked List forward by one position would make its tail become the new head of the linked list.
Whether nodes are moved forward or backward is determined by whether k is positive or negative.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null if it’s the tail of the list.
You can assume that the input Linked List will always have at least one node; in other words, the head will never be None / null.
Sample Input:
head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 # head node has value of 0
k = 2
Sample Output:
4 -> 5 --> 0 -> 1 -> 2 -> 3 # the new head node with value of 4

I already have written both Singly Linked List and Doubly Linked List algorithms with all kinds of methods for popping/appending/getting/inserting/removing. As you can read in the exercise above, it specifically says to complete the task with a “Singly Linked List” but I plan on writing 2 solutions - - one for Singly and one for Doubly. When I first read the challenge, I gravitated towards Doubly first because I encountered a gestalt and the solution for that seems more obivious. Once I have a solution for the Doubly Linked List version, I will return to Singly.

I made three attempts at shifting my DLL and my Python interpreter didn’t like any of them. All three attempts can be found below. Here is my absolute best effort:

def shift_linked_list(DLL_obj,k):
    # if k > 0:
    for iteration in range(0,k):
        DLL_obj.cust_insert(0, DLL_obj.tail)
        DLL_obj.cust_remove(DLL_obj.tail)
    return DLL_obj

shift_linked_list(DLL_obj,2)

Here is the traceback:

Traceback (most recent call last):
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script10.py", line 207, in <module>
    shift_linked_list(DLL_obj,2)
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script10.py", line 204, in shift_linked_list
    DLL_obj.cust_remove(DLL_obj.tail)
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script10.py", line 153, in cust_remove
    if item_location < 0: # or item_location > self.length:
       ^^^^^^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'Node' and 'int'

It’s pointing to my Doubly Linked List custom remove method. You can find my full script and complete DLL algorithm below, including line 153 which is expecting the item_position. In my case I am passing in DLL_obj.tail which is not the position but the value of what is at that position. Right? To get the item_position, I figure I might need to use the Python builtin len() method but that only works on lists and my DLL isn’t a list. This means I can’t use the len() method in this context. My question for all of you: How do I grab the last item position of my DLL? If I can properly do that, I figure I should be able to use it to pass into my cust_remove() method and proceed with shifting a linked list according to k variance.

Here is my full DLL script:

class Node:
    # Create a new node with the value passed to the function
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0


    def add_right(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
        # If not... 
        else:
            # Set the next property on the tail to be that node
            self.tail.next = newNode
            # Set the previous property on the newly created node to be the tail
            newNode.prev = self.tail
            # Set the tail to be the newly created node
            self.tail = newNode
        # Increment the length
        self.length = self.length + 1
        # Return the Doubly Linked List
        return self
    
    
    def pop_right(self):
        # If there is no head, return undefined
        if self.head == None:
            return "Undefined"
        else:
            # Store the current tail in a variable to return later
            temp = self.tail
            # If the length is 1, set the head and tail to be null
            if self.length == 1:
                self.head == None
                self.tail == None
            # Update the tail to be the previous Node
            self.tail = self.tail.prev 
            # Set the newTail's next to null
            self.tail.next = None
        # Decrement the length    
        self.length = self.length - 1
        # Return the value removed
        return temp


    def add_left(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value) # If the length is 0
        if self.length == 0:
            self.head = newNode # Set the head to be the new node
            self.tail = newNode # Set the tail to be the new node
        else: # Oherwise... 
            # Set the prev property on the head of the list to be the new node
            self.head.prev = newNode
            # Set the next property on the new node to be the head property
            newNode.next = self.head
            # Update the head to be the new node
            self.head = newNode
        self.length = self.length + 1 # Increment the length
        return self


    def pop_left(self):
        # If length is 0, return undefined
        if self.length == 0:
            return "Undefined"
        else:
            # Store the current head property in a variable (we'll call it old head)
            old_head = self.head
            # If the length is one 
            if self.length == 1:
                # Set the head to be null 
                self.head == None
                # set the tail to be null
                self.tail == None
            # Update the head to be the next of the old head
            self.head = old_head.next
            # Set the head's prev property to null
            self.head.prev = None
            # Set the old head's next to null
            old_head.next = None
        # Decrement the length
        self.length = self.length - 1
        # Return old head
        return old_head

    def cust_get(self, item_location):
        
        if item_location < 0 or item_location >= self.length:
            return None
        
        if item_location <= (self.length // 2):
            print("Traversing from start")
            count = 0
            current = self.head
            while count != item_location:
                current = current.next
                count = count + 1
            return current
        
        elif item_location >= (self.length // 2):
            print("Traversing backwards from end")
            count = self.length -1
            current = self.tail
            while count != item_location:
                current = current.prev
                count = count - 1            
            return current


    def cust_set(self, item_location, new_value):
        found_node = self.cust_get(item_location)
        
        if found_node != None:
            found_node.value = new_value
            return True
        return False
        

    def cust_insert(self, item_location, new_value):
        if item_location < 0 or item_location > self.length:
           return None
        elif item_location == 0:
            return self.add_left(new_value)
        elif item_location == self.length:
           self.add_right(new_value)
           self.length += 1 
           # print(self.length)
           return self
        new_node = Node(new_value)
        before_node = self.cust_get(item_location-1)
        after_node = before_node.next
        before_node.next = new_node
        new_node.prev = before_node
        new_node.next = after_node
        after_node.prev = new_node
        self.length = self.length + 1
        return True
    

    def cust_remove(self, item_location):
        if item_location < 0: # or item_location > self.length:
           return None
        elif item_location == 0:
            return self.pop_left()
        elif item_location == (self.length-1):
           return self.pop_right()
        removed_node = self.cust_get(item_location)
        removed_node.prev.next = removed_node.next
        removed_node.next.prev = removed_node.prev
        removed_node.next = None
        removed_node.prev = None
        self.length = self.length - 1
        return removed_node
    
    
    def __str__(self):
        if self.length == 0:
            return "Empty DLL for intialization"

        current = self.head
        elements = []
        while current:
            elements += [str(current.value)]
            current = current.next

        return "Doubly Linked List: [" + " <-> ".join(elements) + "]"
      

# Instantiation and testing
    
DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
print(DLL_obj)
DLL_obj.cust_insert(0,999)
print(DLL_obj)
DLL_obj.cust_insert(4,90099)
print(DLL_obj)
DLL_obj.cust_insert(2,"'Custom insert test'")
print(DLL_obj)
# DLL_obj.cust_remove(2)
print(DLL_obj.cust_remove(2))

print(DLL_obj)

Here are two other (failed) attempts I made at writing the shift_linked_list() function:

def shift_linked_list(DLL_obj,k):
    if k > 0:
        for iteration in range(0,k):
            DLL_obj.cust_insert(0, DLL_obj.pop_right())
            DLL_obj.cust_remove(len(DLL_obj)-1)
        return DLL_obj

shift_linked_list(DLL_obj,2)

print(DLL_obj)

And:

def shift_linked_list(DLL_obj,k):
    if k > 0:
        for iteration in range(0,k):
            DLL_obj.add_left(DLL_obj[-1])
            DLL_obj.pop_right(DLL_obj[0])
        return DLL_obj

rgh · July 25, 2024, 2:49pm

You don’t have an absolute position, but you have a Node instance, so you already have prev and next pointers.
To remove the element you can simply update the left and right nodes, plus self.length and (if needed) self.head and/or self.tail
If you absolutely need an absolute position you can traverse the list from start until you find the node

onePythonUser · July 25, 2024, 2:53pm

Hi,

you can try something like this:

class CircularLinkedList:

    def __init__(self):

        self.head = None
        self.nodes = None
        self.node_objects = []

    def traverse(self, starting_point = None):

        if starting_point is None:

            starting_point = self.head

        node = starting_point

        while node is not None and (node.next != starting_point):

            yield node
            node = node.next

        yield node

    def print_list(self, starting_point = None):

        self.nodes = []

        for node in self.traverse(starting_point):
            # nodes.append(str(node))       # Shows node object
            self.nodes.append(node.data)    # Append node data
            self.node_objects.append(node)  # Append node object

        print(" -> ".join(self.nodes))
    
    # Reassigns the head node depending on the value of `k'
    def shift_nodes(self, k_pos):

        if abs(k_pos) < len(self.node_objects):
            self.head = self.node_objects[k_pos]
        else:
            print("'k' value entered exceeds nodes in linked list!")

class Node:

    def __init__(self, data):

        self.data = data
        self.next = None
        self.previous = None

circular_llist = CircularLinkedList()

# Create node objects
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")
g = Node("g")
h = Node("h")

# Set pointer to next node in sequence
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
f.next = g
g.next = h
h.next = a

# Define the head node for the linked list
circular_llist.head = a

# Print initial state of list
circular_llist.print_list()

def shift_linked_list(l_list, k):
    l_list.shift_nodes(k)

shift_linked_list(circular_llist, -5)

# Print post shifted list
circular_llist.print_list()

I borrowed the base code from a website of which I forgot to copy ( as soon as I find it I will copy the link). All I did was add an extra method (shift_nodes) and two attributes to the CircularLinkedList class, and added the function by which to pass the two required parameters: the linked list and the k argument.

Here is the tutorial where I found the base code:

I will not delve much into the theory as the tutorial explains it pretty well.

onePythonUser · July 25, 2024, 3:04pm

By the way, it is technically incorrect to call it a Singly Linked List as that would imply a one way pointer for every node. The correct terminology would be Circular Linked List as per the figure below since the tail node points to the first node:

enoren5 · August 2, 2024, 7:54am

Thank you both for your replies.

This is a good observation. In keeping with the DRY principal, in my latest attempts (two of them below), I reworked my function by embedding it into my original Doubly Linked List class so it it inherits all the properties including self.left / self.right / Node

In my latest two attempts, I didn’t see the requirement of updating self.length because in the context of the coding challenge, I am merely moving a list item from the right end to the left end. This means that the length should always remain the same since I am not remove or adding, just repositioning.

Having said all of that, here is my best attempt:

    def shift_linked_list(self, variance):
        if variance > 0:
            for iteration in range(0,variance):
                self.head = self.tail 
                # self.length = self.length + 1
            return self
        elif variance < 0:
            for iteration in range(0,variance):
                self.tail = self.head
                # self.length = self.length - 1
            return self
        elif variance == 0:
            pass

To test, I build the DLL, print the the DLL, cast the method, and print the new DLL. This gives me a before and after snapshot:

DLL_obj = DoublyLinkedList()
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
DLL_obj.cust_insert(0,999)
DLL_obj.cust_insert(4,90099)
DLL_obj.cust_insert(2,"'Custom insert test'")
print(DLL_obj)

DLL_obj.shift_linked_list(5)
print(DLL_obj)

Here is my expected output:

python script11.py
Traversing from start
Doubly Linked List: [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
Doubly Linked List: [22 <-> 90099 <-> 999 <-> 7 <-> 'Custom insert test' <-> 12 ]

Here is my actual output in my shell:

python script11.py
Traversing from start
Doubly Linked List: [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
Doubly Linked List: [90099]

Take notice that in my expected output the two end values are added to the front but in the actual output it is returning just the single node from the end. I clearly still have issues and I believe the self.length value isn’t it.

Here is a rewrite of the method as my next attempt:

    def shift_linked_list(self, variance):

        if variance > 0:
            for iteration in range(0,variance):
                # Store the current tail in a variable to add later
                temp = self.tail
                # Reassign prev as new tail
                self.tail = self.tail.prev 
                # Set the new tail's next to null
                self.tail.next = None
                # self.length = self.length - 1
                self.head = temp
            return self

        elif variance < 0:
            for iteration in range(0,variance):
                self.tail = self.head
                # self.length = self.length + 1
            return self

        elif variance == 0:
            pass

As you can see, this time I am reassigning prev and next values to the end.

Here is my output now:

python script12.py
Traversing from start
Doubly Linked List: [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
Doubly Linked List: [22]

That is progress because now the variance value is being processed properly. I am getting the second last list item rather than the first. If I change the variance to 3 it returns 12. While this may be a slight improvement, what I really need is my method to return the full list rather than just the one node. What might you people suggest I try to next to achieve that? How close am I to the desired outcome?

Based on the description of the challenge I outlined initially and based on the article you shared, I can see why a “Circular Linked List” kind of makes sense, but the actual original challenge in context I encountered on AlgoExpert as a fair-use “freebie”. This means that Singly Linked List is the right terminology. As I explained originally as well, I in my case I am attempting to write this method on a Doubly Linked List and then afterwards will reimplement as Singly.

Although while I appreciate @onePythonUser sharing their advice and the article, please be advised that I am trying to learn how to write algorithms in Python and by providing all the code kind of ruins the educational experience for me. For anyone reading this, I am asking for your advice, recommendations, feedback, and hints without other forum members providing the entire solution for me. The response that @rgh is perfect because I welcome pseudo code. Further insight along those lines is what I am looking forward to.

rgh · August 2, 2024, 3:38pm

Well, you’re trying to make your job easier by using a doubly linked list.
This is a good idea, but for it to work properly the last and first nodes should be connected as well (i.e. head.prev = tail, tail.next=head), making it a circular linked list.
The second attempt doesn’t work because tail.next and head.prev are both None.
The loop updates the head, tail and new tail.next pointers, but it should also update temp.next and head.prev.

enoren5 · August 5, 2024, 8:42pm

Thank you for your reply.

For the second attempt, you’re right when you observe that I was pointing to None. That’s not where I want to be. You suggested that I should be updating temp.next and head.prev. I experimented with that and encountered a perpetual loop. I tried a few different variations. No dice.

Here was on such next attempt:

    def shift_linked_list(self, variance):

        if variance > 0:
            for iteration in range(0,variance):
                # Store the current tail in a variable to add later
                temp = self.tail
                # Reassign prev as new tail
                self.tail = self.tail.prev 
                # Set the new tail's next to head
                temp.next = self.head
                # self.head.prev = self.tail
                self.tail.next = self.head
            return 

        elif variance < 0:
            for iteration in range(0,variance):
                self.tail = self.head
                # self.length = self.length + 1
            return self

        elif variance == 0:
            pass

I realize that is all wrong because I played around using my debugger as I watched the interpreter build a list with the same variable, over and over. I have a lot of work cut out for me as I continue to use my debugger and rubber ducky my way through the next iteration of my algorithm.

The material from the platform gives this hint:

HINT: There are four nodes that really matter in this entire process: the original tail of the linked list, which will point to the original head of the linked list, the original head of the linked list, which will be pointed to by the original tail of the linked list, the new tail of the linked list, and the new head of the linked list. Note that the new head is the node that the new tail points to in the original, unshifted linked list.

This provides a lot of additional clarity and gives me some more leads to work with. I don’t have enough time today but I will return with more experimentation when I can.

Thank you @rgh for your suggestions so far.

rgh · August 6, 2024, 7:33am

In the posted attempt you set both temp.next and tail.next to the same element.
Obviously it cannot work, because temp is the previous tail and tail is now the new element. temp.next should point to the new tail.
But I’m not sure what is your current list implementation. If you are using a circular list (as tail.next = self.head suggests) shifting can be implemented by just updating the head/tail pointers. Shifting doesn’t really move the elements, it’s just changing the head (and consequently, tail) position.
If you are still using the previous implementation, were tail.next was None, then shifting means changing the elements, as you are trying to do in your example.
At this time, however, I suggest you first draw the list on a piece of paper before and after a single shift. It will be much easier to understand how to implement the changes.

enoren5 · August 10, 2024, 12:41pm

While I didn’t draw a diagram on paper, earlier I shared my expected (desired) output and broken actual output. That was a few posts ago and this thread is rather verbose, so I can’t blame you for missing it, @rgh . Here it is again with some slight reformatting.

Original DLL output:

 [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]

Desired DLL after one shift of last element to front of DLL:

[ 90099 <-> 999 <-> 7 <-> 'Custom insert test' <-> 12 <--> 22 ]

That is what I am trying to accomplish. I understand the objective clearly.

Back to basics, I tried moving the self.head and self.tail pointers as you’ve suggested in this way:

    def shift_linked_list(self, variance):

        if variance > 0:
            for iteration in range(0,variance):
                temp_end = self.tail
                temp_front = self.head
                self.head = temp_end 
                self.tail = temp_front
            return

When I cast DLL_obj.shift_linked_list(1), the output shows: 90999.

Here is another stab in the dark:

    def shift_linked_list(self, variance):

        if variance > 0:
            for iteration in range(0,variance):
                # temp_end = self.tail
                # temp_front = self.head
                self.head = self.tail 
                self.tail = self.head
            return

Same output as the last one, just a single element is returned: 090999.

Based on the “HINT” I quoted above, I feel like I am doing as it suggests as well as what @rgh is suggesting exactly:

I’ve checked all of those boxes in my code as far as I can tell.

Here is what remains outstanding for me to complete which I am at a loss for:

Here is another try:

    def shift_linked_list(self, variance):

        if variance > 0:
            for iteration in range(0,variance):
                self.tail.next = self.head
                self.head.prev = self.tail
            return

That one loops infinitely and returns nothing.

rgh · August 10, 2024, 7:35pm

Hi, I was suggesting to draw the linked list on paper to help you visualize how the pointers need to be updated to achieve your objective.
You called one of the attempts “another stab on the dark”. Drawing the changes on paper should help you identify exactly what steps are needed, instead of blindly trying code changes.
For example, the last try simply repeats tail.next = head and head.prev = tail variance times.
But in a circular doubly linked list tail.next is already equal to the head element. Ditto for head.prev and tail.
If you like a nice discussion of linked lists, perhaps this article could be useful https://www.geeksforgeeks.org/introduction-to-circular-doubly-linked-list/

enoren5 · August 14, 2024, 3:43pm

This is coming in much clearer now. Thank you.

At this point I get the sense that shifting the position of elements from the end to the front cannot be achieved with my custom DLL I brought to the table in my OP (or any DLL for that matter). It’s not as simple as adding one more method to the 9 methods for the DLL that I already have in place. I wish someone could have told me this to begin with.

The assignment courseware does not say “write a Circular Linked List”. It says shift the final items in a Singly Linked List to the front ‘k’ times. I guess what I need to do is scrap my original custom data structure and rewrite a Circular Linked List from scratch.

Thank you for this instructive Geeks for Geeks article. I am going to take this away and work on this.

It’s really not a difficult concept to grasp. I am a visual learner and have a clear image in my mind of how one node always points to two other nodes, before (prev) and after (next), in a circle.

@onePythonUser already provided a visual diagram of a Circular Linked List. I get the picture.

From the article you @rgh shared:

For the last time I understand how I Circular Linked List works. I have a visual.

rgh · August 15, 2024, 1:24pm

Very good.
I’m afraid I wasn’t very clear in my previous responses, sorry.
I suggested drawing diagrams on paper not merely as a static tool to understand how a linked list works, but rather as an aid to visualize how the list changes after a shift.
In other words, I find it helpful to draw the initial state of the list (a Singly Linked List this time)

and then draw the list after a single shift

To me, those images effectively highlight which nodes are changed by the shift and how.

enoren5 · August 18, 2024, 6:24am

Hi @rgh. Thank you for sharing this helpful diagram of the form of a SLL before/after a shift by k variance. I am even more confused now which I guess is a good thing. I’d like to play around with my own diagram to illustrate my next line of questioning. While I could write my own diagram on paper with a pencil / pen, that might make it difficult to share on these forums. Perhaps it would be easier if I used the same diagraming / illustrating tool you used online. Where did you get that from? Was it a website? Or did you just use MSPaint?

If I can use the same visualization tool you used to model my (mis)understanding, this will enable me to continue my effort to wrap my head around shifting position of elements from the end to the beginning of a SLL.

rgh · August 18, 2024, 9:52am

Hi @enoren5, thank you for your kind words.
I’ve used the wonderful plantuml (https://plantuml.com) object diagrams for drawing the examples.
BTW, this is the source of the ‘after’ image

@startuml
left to right direction
hide empty members

object head {
}
object None 
map "Node n-1" as noden1 {
   Data => Next
}
map "Node 2" as node2 {
   Data => Next
}
map "Node 1" as node1 {
   Data => Next
   'Next *--> node2::Next
}
map "Node n" as noden {
   Data => Next
}
head --> noden
node1 --> node2::Next
node2 -[dotted]-> noden1::Next
noden1 --> None
noden --> node1
@enduml

enoren5 · August 26, 2024, 8:18am

Thank you @rgh.

I have taken your tool and sample markup and reworked it to illustrate my approach.

The two crucial changes I made to your baseline worth noting is that with SLL’s, they are not lists / arrays, meaning there are no index values or numbering scheme. (It’s just Node → Node → Node rather than Node 1 → Node 2 → Node 3). The second modification I made was for the “Data” variables which I’ve replaced with placeholder ‘lorem ipsum’ content. This is a personal preference because it makes it easier for me to distinguish one node from the others since numbering them with integers doesn’t quite make sense to me.

Having said all of that, here is the original state of the SLL as I’ve fashioned it:

And then when the last item in the chain is popped off and is added to the front, the SLL is transformed to look like this:

When comparing the two SLL’s, observe the important transformation: The node containing the “sit4” data content was originally at the end as the last node and then it is popped from the right and then added to the left so it becomes the first node in the sequence.

My sample UML markup

@startuml
!theme vibrant
left to right direction
hide empty members

object head {
}

object None 

' map "Node n-1" as noden1 {
'   Data => Next
' }

map "Node" as node4 {
   "sit4" => Next
}
map "Node" as node3{
   "dolor3" => Next
}
map "Node" as node2 {
   "ipsum2" => Next
}
map "Node" as node1 {
   "lorem1" => Next
}

' map "Node n" as noden {
'    Data => Next
' }

head --> node1
'noden --> node1
node1 --> node2
node2 --> node3
node3 --> node4
node4 --> None
@enduml

rgh · August 26, 2024, 9:21am

Very good, tailor the drawing as you need to best understand how to implement the node changes.