CODEWITHSUNDEEP
pythonlistlinked-list
Unknown
Unknown

Reputation: 676

Linked Lists Python 2.7

I'm having trouble trying to implement a linked List without using classes(we're not there yet in my course), and google hasn't helpful at all. Every linked list example uses classes, which I haven't covered. I can create a linked list that adds a value to the beginning of the linked list, but I don't know how to traverse the list and add value after a specific node. Any help would be appreciated. The hardest part for me is figuring out how to traverse the list. 

def addValue(linkedSet, value):
    """
    Adds a new element to a set.
    Parameters:
        the set to be changed (address of the first node)
        the new value to add to the set
    Return result: pointer to the head of the modified set.  This is
        usually the same as the linkedSet parameter, unless the value
        added is less than any value already in the set.

    If the value is already in the set, return the set unchanged.
    This is not an error.
    """
    newNode={}
    newNode['data']=value
    node=linkedSet
    if linkedSet==None:
        newNode['next']=None
        return newNode
    if member(linkedSet,value)==True:
        return linkedSet
    elif linkedSet['next']==None:
        newNode['next']=None
        linkedSet['next']=newNode
    elif linkedSet['next']!=None:
        return linkedSet

Upvotes: 1

Views: 868

Answers (3)

jdi
jdi

Reputation: 92637

Just as a general outline of what I think your addValue() function might look like...

def addValue(linkedSet, value):

    newNode={
        'data': value,
        'next': None
    }

    # if linkedSet is None, then you can just return this newNode

    # if linkedSet isnt None...
        # if linkedSets next is None, then it should just point to this newNode 
        # (append)

        # otherwise, you should set its current next to the next of this newnode,
        # and then set its next to this newNode (insert)

This is for a general linked list. It seems like you are suggesting that yours is a more specialized version that maintains a value sort, and always expects to be passed the head node of the list. Yours would require constant looping over each 'next' until it found one where the value was greater than the current, and then insert itself by shifting around the 'next' references of the following (and possibly previous) elements.

Upvotes: 2

Jochen Ritzel
Jochen Ritzel

Reputation: 107736

unless the value added is less than any value already in the set sounds like this list is supposed to be sorted. So you go through the list, find the first item larger than your value and splice it in there.

You traverse the list by keeping track of the current node:

def addValue(linkedSet, value):

    newNode={}
    newNode['data']=value
    newNode['next'] = None

    #traverse list
    current = linkedSet
    while True: 
        if current['value'] == value: 
            return linkedSet # it was already in that list

        if current['value'] > value:
            # new node is the new head
            newNode['next'] = linkedSet
            return newNode # new head

        if current['next'] is None:
            # new tail
            current['next'] = new_node
            return linkedSet

        if current['next']['value'] > value:
            # new node belongs here, splice it in
            next_node = current['next']
            current['next'] = newNode
            newNode['next'] = next_node
            return linkedSet

        # didnt return so far, try the next element:
        current = current['next']

Upvotes: 1

mkvcvc
mkvcvc

Reputation: 1565

How about using dictionary as linked list descriptor? Something like:

linkedSet = {'first':firstNode, 'last':lastNode}

Then when you need to travers you could always start from first node, and when you need to add you have your end node.

Upvotes: 0

Related Questions