Inserting Node into a Linked List

H.H.

I want to create a function that inserts a node into any place in a linked list. There is a test function to test if the function works. My problem is that when I run the test function none of the outputs show, any ideas?

"""
Creates and returns a linked list containing all of the elements
of the Python-style list parameter.
"""

def createList(plist):
    myList = None
    # goes backwards, adding each element to the beginning
    # of the list.  
    for index in range(len(plist)-1, -1, -1):
        myList = insertValueHead(myList, plist[index])
    return myList

'''
Creates a string representation of the values in the linked list such as:
5->6->9->14.
'''

def listString(myList):
    ptr = myList
    str1 = ''
    while ptr != None:
    str1 += str(ptr['data'])
    ptr = ptr['next']
    if ptr != None:
      str1 += "->"
    str1 = str1
    return str1

'''
Inserts a new node containing the value "value" to the head of the list.
LinkedList is the head of the list to be added to
Value is the data to be stored in the node'''


def insertValueHead(myList, value):
    newnode = {}
    newnode["data"] = value
    #set the next pointer of this new node to the head of the list, linkedList
    #newnode is now the head of the list 
    newnode["next"] = myList
    return newnode


def insertNode(myList, index, value):
    if index == 0:
        newnode = {}
        newnode["data"] = value
        newnode["next"] = myList

    elif index > 0:
        newnode = {}
        newnode["data"] = value
        ptr = myList
        count = 0
        while ptr != None and count < index-1:
            ptr = ptr['next']
            print count
            count += 1
        return ptr
        newnode['next'] = ptr['next']
        ptr['next'] = newnode

def testInsert():
    #test code to ensure that insertNode is working correctly.
    myList = createList([1, 2, 3, 4, 5, 6])
    print "The initial list", listString(myList)
    #insert 0 at the head
    myList = insertNode(myList,0, 0)
    print "Inserted 0 at the start of list: ", listString(myList)
    #insert 7 at the end
    myList = insertNode(myList, 7, 7)
    print "Inserted 7 at the end of list: ", listString(myList)
    myList= insertNode(myList, 3, 2.2)
    print "Inserted 2.2 in the 3rd position: ", listString(myList)
    myList = insertNode(myList, 26, 12)   #should generate an error

testInsert()
Martijn Pieters

Your insertNode() function never returns newnode when inserting at index 0. As such, None is returned instead.

Since that's the first operation that the testInsert() function does after building the initial linked list, myList in that function is now None and the rest of the test is invalid.

For the index > 0 case, your return statement comes too early; you return ptr, e.g. the node at index - 1 before inserting the new value. All statements after that return statement are not executed.

You don't need to special-case the index = 0 case, really. Here is a better version:

def insertNode(myList, index, value):
    newnode = {'data': value, 'next': None}
    retval = myList if index else newnode 
    prev, ptr = None, myList
    while ptr is not None and index > 0:
        prev, ptr = ptr, ptr['next']
        index -= 1
    if index > 0:
        raise ValueError('Index out of range')
    newnode['next'] = ptr
    if prev is not None:
        prev['next'] = newnode
    return retval

This version actually raises an error if you try to insert a value past the end; index will be greater than 0 in that case.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

inserting node to linked list in c

From Dev

Inserting Node in a Sorted linked list

From Dev

inserting node at beginning of linked list

From Dev

Inserting a node at the end of linked list

From Dev

Inserting a node at the end of a linked list

From Dev

inserting node at beginning of linked list

From Dev

Inserting a node in the end of a linked list

From Dev

Inserting a node in a pre sorted linked list

From Dev

Inserting a node into a sorted doubly linked list

From Dev

Singly linked list in C(Inserting a node)

From Dev

Linked list - Inserting in middle, linking new node

From Dev

Inserting a node at the end of linked list, .exe crashes

From Dev

Inserting a node at the end of a doubly linked list

From Dev

Inserting a node into a sorted doubly linked list

From Dev

inserting a node at the end of linked list recursivly

From Dev

Inserting a node at a specific position in a Linked list

From Dev

Inserting node at beginning of singly linked list

From Dev

Inserting a node before a given node in doubly linked list

From Dev

Inserting a new node into a doubly linked list after a given node

From Dev

Program Freezes When Inserting A New Node To A Linked List

From Dev

Unexpected value after inserting node at the end of linked list

From Dev

Inserting Into Linked List Python

From Dev

Inserting linked list at the end

From Dev

Linked list inserting with two constraints

From Dev

Why doesn't he following code works in inserting node at a specific postion in a Linked List?

From Dev

Linked List Delete Node

From Dev

Deleting a node in a linked list

From Dev

Appending node to linked list

From Dev

Deleting node in linked list

Related Related

HotTag

Archive