[izthrower]

Hey everyone, im looking for a tutorial to implement a doubly linked list in python, i have the code for a
singly linked list but cant get it to work as a doubly linked list. Anyone have a Tutorial?
Thanks

[Simown]

How "can't you get it to work as a doubly linked list"? It's probably beneficial to you to understand how it works rather than copy-pasting, although I do realise you are looking for a tutorial rather than a handout.

I don't know of any reputable tutorial on this in Python, however, if you show us your working so far and what you are trying to achieve, I'm sure we can help out.

This post has been edited by Simown: 29 March 2012 - 08:07 AM

[atraub]

I started writing one, but unfortunately, I built the list, took a break from the tutorial, and then forgot why I did half the things I did. I probably still have the code for the doubly linked list though

I might even have the first half of the tutorial too, but it is unfinished.

This post has been edited by atraub: 29 March 2012 - 08:12 AM

[Motoma]

Hey, if you post the code you've started writing for the double-linked list, we'll be happy to help you move forward from there.

[atraub]

This could be a fun project, I'll post my code, and the in-progress tutorial, maybe you guys can help me remember where I was going with it.

When I get home tonight, I'll post it.

[izthrower]

Hey thanks for the replies, unfortunatly i am not at my school computer that has the code right now but
i should be there tomarow to put the code up. This is basiclly whats going on, our teacher wrote a
program for a singly linked list that uses a dummy node at the beginng. So im working on changing that
two a doubbly linked list with dummy nodes at the beginning and end of the list. The only things ive changed
so far is in one of the classes i changed so you can pass the next node,previous node and the data in the current node.
Also i added a couple of functions of the previous node as well. But whats happening is every time i test to
see what the previous node is it only prints out zero. Also the program has a second file for unit testing but
im not sure if you guys want to see that program as well.
Thanks

[atraub]

Ok here's the old writeup I had

Quote

This tutorial builds a more advanced Data Structure based on the Singly Linked List created here. The previous tutorial is a prerequisite for this one.

The Singly Linked List is a good data structure, but it had some limitations. Many of these limitations were caused by the fact that Nodes can only move forwards, not backwards.

• Slices are O(n**2) because the list has to be searched for each element, particularly when going backwards.
  
• Getting the last element of the list takes a long time because we must first step through every element before it. (Append needs the last element)

Being able to iterate in both directions will help us alleviate these issues. For a better Linked list we'll need a better class of Node (ha hah!!). Transforming a Single-Link Node to a double-link node is simple and straightforward.

__author__ = "Adam Traub"
__date__="1/26/2011"


class LinkedList:
    '''Linked List'''
    class __Node:
        '''
private node object.  Node's consist of an element
and a pointer to the previous and next Node'''
        def __init__(self, element=None):
            self.__element = element
            self.__next = None
            self.__previous = None

        def __str__(self):
            '''string representation of Node'''
            return str(self.__element)

        def hasNext(self):
            '''returns true if the Node has a next Node'''
            return self.__next != None

        def getNext(self):
            '''get next Node'''
            return self.__next

        def setNext(self,nextItem):
            '''set the next Node of the Node'''
            self.__next = nextItem
        
        def hasPrevious(self):
            '''returns true if the Node has a previous Node'''
            return self.__previous != None

        def getPrevious(self):
            '''get previous Node'''
            return self.__previous

        def setPrevious(self,previousItem):
            '''set the previous Node of the Node'''
            self.__previous = previousItem

        def getPreviousAndNext(self):
            '''gets previous and next Nodes'''
            return self.__previous,self.__next 

        def setPreviousAndNext(self, previousItem, nextItem):
            '''set the previous and Next Node of the Node'''
            self.__previous = previousItem
            self.__next = nextItem

        def getElement(self):
            '''get the element of the Node'''
            return self.__element           

        def setElement(self, element):
            '''set the element of the current Node'''
            self.__element = element

As a rule, I'm making all the class attributes private. There's no reason they should ever be directly accessed. It's a habit I'm trying to force upon myself and I recommend you do the same. The changes all center around having a link to a previous element. Could I create a constructor that also allowed for a front and previous optional parameter, sure, why not? I didn't implement it but that doesn't mean someone else can't. Little customizations like that are not the point of this tutorial.

Being able to go backwards gives us some advantages. For example, a 'last' element becomes far more useful to us. Could I have implemented a 'last' node before? Yes, and it would have been useful for appending but worthless for popping. Think about it . Now that we can move backwards the 'last' node will be excellent for popping and appending. We might be able to find some other uses for it as well. You may be inclined to create a second sentinel, but I'd encourage you not to do that. The 'front' sentinel is great because we can gloss over some minor details regarding empty Lists, but we don't need two for that. Instead, I think it will be easy just to keep track of which Node is the last Node with a variable. Here's the new constructor for The Doubly Linked List:

    def __init__(self):
        '''Creates the LinkedList'''
        self.__first = LinkedList.__Node()
        self.__last = self.__first
        self.__length = 0

The new constructor is almost identical to the original constructor, only 1 extra line. With only 1 Node, the first is also the last. Simple, right?

Unfortunately, now that nodes have two links, inserting and popping will be a little painful. Imagine we have [a]<->]c] and we want to insert [b] between them we have to:

• Change [a]'s 'next' to point at [b]
  
• set [b]'s previous to point at [a]
  
• set [b]'s next to point at [c]
  
• set [c]'s previous to point at [b]

That's a lot of stuff to deal with on any given insert. We also have to deal with reassigning 'first' and 'last' as needed. That's a lot of linking to handle, so creating a method to handle it seems appropriate. Here it is:

    def __handleLinking(self, center, previous, nextNode, isRemoving):
        '''takes care of linking Nodes on inserts and removals'''
        def updateLinks(center, previous, nextNode, newNext, newLast, newPrevious, toAdd):
            '''A nested function to reduce repeated code in setting links'''
            if previous != None:
                previous.setNext(newNext)

            if nextNode == None:
                self.__last = newLast
            else:
                nextNode.setPrevious(newPrevious)
            self.__length += toAdd
            
            
        if isRemoving:
            updateLinks(center, previous, nextNode, nextNode, previous, previous, -1)
        else:
            center.setPreviousAndNext(previous,nextNode)
            updateLinks(center, previous, nextNode, center, center, center, 1)

def __handleLinking(self, center, previous, nextNode, isRemoving) This method handles all the linking for inserting and removing a Node.

The more complex submethod updateLinks(center, previous, nextNode, newNext, newLast, newPrevious, toAdd) is used to reduce repeated code.

With this method in place, append is trivial:

    def append(self, element):
        '''Add element to last position of the list'''
        self.__handleLinking(LinkedList.__Node(element),self.__last,None,False)

Pop becomes very simple as well:

    def pop(self, index =None):
        '''Removes and returns an element in the list. last element by default.'''
        if self.__length == 0:
            raise IndexError("pop from empty list")
        
        #utilize default parameter    
        if index ==None: 
            index = self.__length-1
        
        toRemove = self.__getNodeAtPosition(self.__checkIndex(index))        
        self.__handleLinking(toRemove,toRemove.getPrevious(),toRemove.getNext(),True)
        return toRemove.getElement()

Same with insert:

    def insert(self, index, element):
        '''inserts an element to the given index'''
        toMove = self.__getNodeAtPosition(self.__checkIndex(index))
        self.__handleLinking(LinkedList.__Node(element),toMove.getPrevious(),toMove,False)

Very simple stuff thanks to handleLinking.


Now comes the fun part; fixing part of

That's all I had, Here's the corresponding/completed code:

__author__ = "Adam Traub"
__date__="2/16/2011"


class LinkedList:
    '''Linked List'''
    class __Node:
        '''
private node object.  Node's consist of an element
and a pointer to the previous and next Node'''
        def __init__(self, element=None):
            self.__element = element
            self.__next = None
            self.__previous = None
            self.__toMove = (self.getPrevious,self.getNext)

        def __str__(self):
            '''string representation of Node'''
            return str(self.__element)

        def hasNext(self):
            '''returns true if the Node has a next Node'''
            return self.__next != None

        def getNext(self):
            '''get next Node'''
            return self.__next

        def setNext(self,nextItem):
            '''set the next Node of the Node'''
            self.__next = nextItem
        
        def hasPrevious(self):
            '''returns true if the Node has a previous Node'''
            return self.__previous != None

        def getPrevious(self):
            '''get previous Node'''
            return self.__previous

        def setPrevious(self,previousItem):
            '''set the previous Node of the Node'''
            self.__previous = previousItem

        def getPreviousAndNext(self):
            '''gets previous and next Nodes'''
            return self.__previous,self.__next 

        def setPreviousAndNext(self, previousItem, nextItem):
            '''set the previous and Next Node of the Node'''
            self.__previous = previousItem
            self.__next = nextItem

        def getElement(self):
            '''get the element of the Node'''
            return self.__element           

        def setElement(self, element):
            '''set the element of the current Node'''
            self.__element = element

        def get(self,gettingNextElement):
            '''Get element based on a boolean.  True for next.  False for previous'''
            return self.__toMove[int(gettingNextElement)]()
            

    def __init__(self):
        '''Creates the LinkedList'''
        self.__first = LinkedList.__Node()
        self.__last = self.__first
        self.__length = 0

    def __len__(self):
        '''returns the length of the list O(1)'''
        return self.__length

    def count(self):
        '''returns the length of the list O(1)'''
        return self.__length

    def isEmpty(self):
        '''returns true if the list is empty'''
        return self.__length == 0

    def append(self, element):
        '''Add element to last position of the list'''
        self.__handleLinking(LinkedList.__Node(element),self.__last,None,False)
                    
    def pop(self, index =None):
        '''Removes and returns an element in the list. last element by default.'''
        if self.__length == 0:
            raise IndexError("pop from empty list")
        
        #utilize default parameter    
        if index ==None: 
            index = self.__length-1
        
        toRemove = self.__getNodeAtPosition(self.__checkIndex(index))        
        self.__handleLinking(toRemove,toRemove.getPrevious(),toRemove.getNext(),True)
        return toRemove.getElement()

    def insert(self, index, element):
        '''inserts an element to the given index'''
        toMove = self.__getNodeAtPosition(self.__checkIndex(index))
        self.__handleLinking(LinkedList.__Node(element),toMove.getPrevious(),toMove,False)

    def extend(self, toAdd):
        '''extend current list by adding an iterable structure to the end'''
        for value in toAdd:
            self.append(value)

    def index(self, x):
        '''Find index of first ocurrence of a given value'''
        for dex,value in enumerate(self):
            if x == value:
                return dex
        raise ValueError("LinkedList.index(x): x not in list")

    def reverse(self):
        '''reverse the linked list'''
        for index in range(self.__length-1,-1,-1):
            self.append(self.pop(index))

    def __getitem__(self, index):
        '''Allows for indexing, index must be an integer'''
        #accounts for slicing
        if type(index) == slice:
            return self.__sliceList(index)
        return self.__getNodeAtPosition(self.__checkIndex(index)).getElement()

    def __add__(self, other):
        '''adds a an iterable data structure to the linked list'''
        retList = LinkedList()
        for item in self:
            retList.append(item)
        for item in other:
            retList.append(item)
        return retList

    def __setitem__(self, index, element):
        '''Sets the item at a given index to a new element.'''
        self.__getNodeAtPosition(self.__checkIndex(index)).setElement(element)

    def __str__(self):
        '''returns a string representation of the list'''
        if self.__length == 0:    
            return '[]'
        retString = "["
        currentElement = self.__first.getNext()
        for i in range(self.__length):
            retString += str(currentElement) +", "
            currentElement = currentElement.getNext()
        
        return retString[:-2] + ']'


    #Private functions
    def __handleLinking(self, center, previous, nextNode, isRemoving):
        '''takes care of linking Nodes on inserts and removals'''
        def updateLinks(center, previous, nextNode, newNext, newLast, newPrevious, toAdd):
            '''A nested function to reduce repeated code in setting links'''
            if previous != None:
                previous.setNext(newNext)

            if nextNode == None:
                self.__last = newLast
            else:
                nextNode.setPrevious(newPrevious)
            self.__length += toAdd
            
            
        if isRemoving:
            updateLinks(center, previous, nextNode, nextNode, previous, previous, -1)
        else:
            center.setPreviousAndNext(previous,nextNode)
            updateLinks(center, previous, nextNode, center, center, center, 1)
            
                                
    def __sliceList(self,theSlice):
        '''(Private) function to handle slicing.  Returns a Linked List'''
        def determineStartStopStep(valToCheck, step, positiveStep, negativeStep):
            '''nested function to reduce repeated code in determining slicing handling'''
            if valToCheck == None:
                if step > 0:
                    return positiveStep
                else:
                    return negativeStep
            else:
                return valToCheck
            

        retList = LinkedList()        
        #Following conditions handles the x[start:stop:step] notation
        step  = determineStartStopStep(theSlice.step,1,1,1)
        start = determineStartStopStep(theSlice.start,step,0,self.__length-1)
        stop  = determineStartStopStep(theSlice.stop,step,self.__length,-1)

        currentNode = self.__getNodeAtPosition(start)
        gettingNext = step > 0
        absStep = abs(step)

        for eachItem in range(start,stop,step): 
            retList.append(currentNode)
            if eachItem + step <= stop:#prevents step from going out of bounds
                for i in range(absStep):
                    currentNode = currentNode.get(gettingNext)
        return retList

    
        
    def __getNodeAtPosition(self, index):
        '''(Private) Gets a Node at a given index'''
        movingForward = index < (self.__length//2)-1
        if movingForward:
            currentNode = self.__first
            toAdd = 1
        else:
            currentNode = self.__last
            index = (self.__length-1) - index
            toAdd = 0

        """
        Putting the for loop inside the condition would reduce the amount
        of times the conditon must be evaluated, increasing efficiency
        But would also simultaneously increase the amount of repeated code
        """
        for i in range(index+toAdd):
            currentNode = currentNode.get(movingForward)
        
        return currentNode

    def __checkIndex(self, index):
        '''(Private) check if the index is an acceptable value.  Index only changes if negative'''
        if type(index) != int:
            raise TypeError("Index must be an integer or a slice not a "+str(type(index)).split("'")[1])

        #handles negative indices.
        if index < 0:
            index += self.__length

        #If the index is out of bounds
        if index >= self.__length or index < 0:
            raise IndexError("Index out of bounds")
    
        return index
        
if __name__ == "__main__":
    import random
    def advanceWMessage(message):
        input(message+" press enter to continue")
    def printList(theList):
        print("Current List:"+str(theList))
        
    x = LinkedList()
    for i in range(30):
        x.append(i)
        
    printList(x)
    advanceWMessage("Testing slicing")
    for i in range(10):
        val1 = random.randint(0,len(x)//2)
        val2 = random.randint(len(x)//2,len(x))
        val3 = random.randint(1,len(x)//10)
        print("\n\nstart: "+str(val1))
        print("stop: "+str(val2))
        print("step: "+str(val3))
        print(x[val1:val2:val3])

    advanceWMessage("Insert -1 at beginning")
    x.insert(0,-1)
    printList(x)
        
        

When I look at it now, I don't fully understand what I was doing. It's an advanced inplementation, I think. Haha I know it all made sense to me a year ago

This post has been edited by atraub: 29 March 2012 - 06:48 PM

[Simown]

@atraub Woah, that looks like a pretty in depth linked-list. I think only you may be able to unravel its mysteries. I'm sure I could help figure what was going on out with you if found it necessary, I have been studying linked-lists in every possible context during my degree for the past year or so.

@izthrower so your list is in this sort of format?

class DoublyLinkedList

    def __init__(self):
        self.listStart = None
        self.listEnd = None

        class Node:
    
            def __init__(self, value, prev, next)
               self.value = value
               self.prev = prev
               self.next = next

With the listStart pointing to the first node and the listEnd pointing to the last node in the list. Maybe you have two classes instead of an inner class. I think I understand what you described; it seems like we'd have to see some code before guessing any further at possible steps.

This post has been edited by Simown: 29 March 2012 - 07:05 PM

[izthrower]

class Node(object):

    def __init__(self, data = None,next = None,pre = None):
        self._data = data
        self._next = next
        self._pre = pre
    
    def getData(self):
        return self._data

    def getNext(self, other):
        return self._next

    def getPre(self,other):
        return self._pre

    def setData(self, data):
        self._data = data

    def setNext(self, next):
        self._next = next

    def setPre(self,pre):
        self._pre = pre
 
    def __str__(self):
        return str(self._data)

    def __repr__(self):
        return "Node(%s, %s)" % (repr(self._data), repr(self._next))

    def __eq__(self, other):
        return self._data == other._data and self._next == other._next

#----------------------------------------------------------------------------

class LinkedList(object):
    # (Singly) linked list.
    # Constructed with a dummy node at the begginig of the list.
    # Stores a reference to the dummy node and stores list's length.

    def __init__(self):
        # To do: allow a Python list or tuple as a parameter.
        self._length = 0
        self._first = Node(None, None,None)
        self._last = Node(None,None,None

    def __len__(self):
        # Special method. Used by built-in function length
        return self._length

    def _insertItemAfterNode(self, item, aNode):
        # Private method
        newNode = Node(item, aNode._next)
        aNode._next = newNode
        self._length += 1

    def _nodeBeforeIndex(self, index):
        # Private method
        if 0 <= index <= self._length:
            i = -1
            aNode = self._first
            for i in range(index):
                aNode = aNode._next
            return aNode
        else:
            raise IndexError

    def __getitem__(self, index):
        # Special method. Used by rhs indexed expression.
        # ... = mylist[3], print(mylist[3])
        return self._nodeBeforeIndex(index)._next._data

    def __setitem__(self, index, item):
        # Special method. Used by lhs indexed expression.
        # mylist[3] = ...
        self._nodeBeforeIndex(index)._next._data = item

    def insertItemAtTheFront(self, item):
        self._insertItemAfterNode(item, self._nodeBeforeIndex(0))

    def insertItemAtTheEnd(self, item):
        self._insertItemAfterNode(item, self._nodeBeforeIndex(self._length))

    def insertItemAtIndex(self, index, item):
        '''Valid range 0 <= index <= length.'''
        self._insertItemAfterNode(item, self._nodeBeforeIndex(index))

    def __iter__(self):
        # Special method. Returns iterator.
        return LinkedListIterator(self)

    def __repr__(self):
        # Special method. In the absence od __str__ it is used by print.
        plist = []
        for item in self:
            plist.append(item)
        return "LinkedList(%s)" % str(plist)

#----------------------------------------------------------------------------

class LinkedListIterator(object):

    def __init__(self, alist):
        self._list = alist
        self._currentIndex = -1
        self._currentNode = self._list._first

    def __iter__(self):
        # Any iterator must have __iter__ method that returns self.
        return self

    def __next__(self):
        # Any iterator must have __next__ method such that 
        # it possibly raises StopIteration and 
        # if it raises StopIteration than it raises it on even subsequent call.
        if self._currentIndex == self._list._length - 1:
            raise StopIteration
        else:
            self._currentIndex += 1
            self._currentNode = self._currentNode._next
            return self._currentNode._data
        return

This is the code so far ive added all the previous node stuff. Honistly this could be correct but i havent been able to run any tests
on it to make sure. Any ideas?


@atraub
when i read your code i started bowing at my computer then i started getting weird looks from the other people in the computer lab...

This post has been edited by izthrower: 30 March 2012 - 07:16 AM

[baavgai]

izthrower, on 29 March 2012 - 01:47 PM, said:

our teacher wrote a program for a singly linked list that uses a dummy node at the beginng

That's already a bad start... Seriously, poor design.

Simown has a more reasonable start. Depending on what you're doing, you don't even need a tail.

Here's a bare bones singly linked list:

class LinkedList(object):
	def __init__(self):
		self.head = None
		
	def add(self, value):
		self.head = [ value, self.head ]
		
	def isEmpty(self): 
		return self.head == None
	
	def display(self):
		p = self.head
		while p:
			(val, next) = p
			print val
			p = next


ll = LinkedList()
print ll.isEmpty()
ll.add(1)
ll.add(2)
ll.add(3)
print ll.isEmpty()
ll.display()

First define what methods your linked list class is going to have. The user of your class shouldn't care how the node or list is implemented; just about the methods you give them.

[izthrower]

Ok so apperentlly what ive done does work, the only problem is the way you have to define the nodes
in the unittest program you have to use non existing variables that are defined in the next line,
Example:

    n3 = Node(3,None,n2)
    n2 = Node(2,n3,n1)
    n1 = Node(1,n2,None)

And the problem is that if i do define them before (example n2=0,n1=0) the zeros pass over when i use the getPre function in the Node class. Any idea on a way around this?

[atraub]

Thanks guys, I was a little self-conscious showing code that I haven't worked on in over a year and can't fully understand. It is intense though. I really don't understand everything I did in it, it may be a lost treasure of DreamInCode... but it does work and you're all free to play with it. It should prove to be a very powerful structure.