0

Basically, I'm implementing a LinkedList class and then implementing various methods to use it. Below is the code for the LinkedList class(and its dependent Node class)

# A simple linked list implementation

class Node:
# attributes:
#   data (can be anything)
#   next (another Node)

    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
# attributes:
#   head (a Node)
# ****************
# methods:
#   insert
#   find
#   delete

    def __init__(self):
        self.head = None

    def __str__(self):
        output = []
        current_node = self.head
        while current_node:
            output.append(str(current_node.data))
            current_node = current_node.next
        return(", ".join(output))


    # Creates a Node with the given data and inserts into the front of the list.
    def insert(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # Finds the first node with the given data. Returns None if there is no such node.
    def find(self, data):
        current_node = self.head
        while(current_node):
            if (current_node.data == data):
                return current_node
            current_node = current_node.next
        return None # We reached the end of the list without finding anything.

    # Deletes given node. Can be used in conjunction with find.
    def delete(self, deleted_node):
        if deleted_node == self.head:
            self.head = self.head.next
            return
        current_node = self.head
        while(current_node.next != deleted_node):
            current_node = current_node.next
        current_node.next = deleted_node.next

Then, I'm trying to implement a rotate(my_list, N) function, which will, well, rotate my_list by N. The following is my code:

import linkedlists as ll
from ErrorHandler import sanitize
import random, math, time, copy

def length(my_list):
    sanitize(my_list, ll.LinkedList)
    if my_list.head == None: return 0
    count = 1 #First item! Ah, ah, ah
    current_node = my_list.head
    while current_node.next != None:
        current_node = current_node.next
        count += 1 #One more item! Ah, ah, ah
    return count

def get_Nth(my_list, N):
    sanitize(my_list, ll.LinkedList)
    if my_list.head == None: return None
    current_node = my_list.head
    count = 0
    while current_node.next != None:
        if count == N:
            return current_node
        count +=1
        current_node = current_node.next
    return current_node

def rotate(my_list, N):
    sanitize(my_list, ll.LinkedList)
    if my_list.head == None: return None
    N = N % length(my_list)
    lent = length(my_list)
    get_Nth(my_list, lent-1).next = my_list.head
    my_list.head = get_Nth(my_list, lent-N)
    get_Nth(my_list, lent-N-1).next = None

However, calling rotate() on a LinkedList containing the numbers from 0 to 9 in ascending order returns 8,9,0,1,2,3,4,5. Why? I'm pretty sure it has to do with the third- and second-to-last lines, because when assigning get_Nth(my_list, lent-1).next to my_list.head, it only points to my_list.head, instead of the Node object my_list.head points to at the time.

How can I fix this?

2
  • What does sanitize do? Also, by rotate do you mean rotate one over to the right? Is the expected output [9, 0, 1, 2, 3, 4, 5, 6, 7, 8]? Commented Sep 16, 2018 at 2:14
  • sanitize, well, sanitizes the inputs. And yes, that is the expected. Commented Sep 16, 2018 at 5:06

1 Answer 1

1

Your error is right here: get_Nth(my_list, lent-N-1).next = None

I'm assuming you called rotate(my_list, 2) so at this point, the list looks like this [8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, ...]. So when you call get_Nth(my_list, lent-N-1), lent-N-1 is 7, and well, the element at index 7 is actually 5.

You should just use lent-1.

Sign up to request clarification or add additional context in comments.

1 Comment

Right! I forgot that at this point I've shifted the list over. Thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.