#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    2
    Rep Power
    0

    Stack implement Linked List


    Hey guys i'm new to Python and have been trying to do an old homework question that requires me to write an implementation of a linked list.

    At the moment it is not passing all of the doctests.

    This is what I have so far:

    Code:
    '''Data structures implemented with linked lists.'''
    
    class Node:
        '''A node for a linked list.'''
        def __init__(self, initdata):
            self.data = initdata
            self.next_node = None
    
    class Stack (object):
        """ Implements a Stack using a Linked List"
        >>> s = Stack()
        >>> print(s)
        List for stack is: None
        >>> result = s.pop()
        Traceback (most recent call last):
        ...
        IndexError: Can't pop from empty stack.
        >>> s.push('a')
        >>> print(s)
        List for stack is: a -> None
        >>> s.length()
        1
        >>> s.pop()
        'a'
        >>> print(s)
        List for stack is: None
        >>> s.push('b')
        >>> print(s)
        List for stack is: b -> None
        >>> s.push('c')
        >>> print(s)
        List for stack is: c -> b -> None
        >>> s.length()
        2
        >>> s.peek()
        'c'
        >>> print(s)
        List for stack is: c -> b -> None
        >>> s.pop()
        'c'
        >>> print(s)
        List for stack is: b -> None
        """
    
        def __init__(self):
            self.head = None
    
        def push(self, item):
            """push a new item on to the stack"""
          
            temp = Node(item)
            temp.next_node = item
            self.head = temp
        
    
        def pop(self):
            """pop an item off the top of the stack, and return it
            If stack is empty you should raise an IndexError as per
            the comment below."""
          
            if self.isEmpty():
                raise IndexError('Can\'t pop from empty stack.')
            else:
                temp = self.head.data
                self = self.head.next_node
                return temp
           
            # use the following if stack is empty
            # raise IndexError("Can't pop from empty stack.")
    
        def peek(self):
            """pop an item on the top of the top of the stack, but don't remove it"""
          
            
              
            return   self.head.data
       
    
        def isEmpty(self):
            return self.head == None
    
        def length(self):
           
            count = 1
            for items in self.head.next_node:
                count = count + 1
                
            return count
           
    
        def __str__(self):
            """Returns a string representation of the list for the stack starting 
            from the begining of the list. Items are seperated by -> 
            and ending with -> None
            See doctests in class docstring
            """
          
           
            
            list = ""
            for i in str(self.head.data):
                list += i + " -> "
                
                
            list += "None"     
                
            return  list
          
    
    
    
    
    if __name__ == '__main__':
        import doctest
        import os
        os.environ['TERM'] = 'linux'  # Suppress ^[[?1034h
        # Uncomment the testmod() line to run the tests
        # Can enter an infinite loop if your Stack isn't implemented correctly
        doctest.testmod()
    What i'm most confused about it the Pop() and print() function . Any advice is appreciated!
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,904
    Rep Power
    481

    repaired.


    I disapprove of projects, like this, which try to turn python into c or java. There are better ways to construct stacks in python. Use a list directly with pop and append methods.

    class STACK has 16 lines versus the 58 lines of class Stack, which also requires the node class. And it is faster. (An untested claim.) And simpler.

    You'll still need to repair your pop method. You had more questions than you knew.
    Code:
    class Node:
        '''A node for a linked list.'''
        def __init__(self, initdata):
            self.data = initdata
            self.next_node = None
    
    class Stack (object):
    
        ''' 
            Data structures implemented with linked lists.
    
    
            Implements a Stack using a Linked List"
            >>> s = Stack()
            >>> print(len(s))
            0
            >>> print(s)
            List for stack is: None
            >>> result = s.pop()
            Traceback (most recent call last):
            ...
            IndexError: Can't pop from empty stack.
            >>>                                                 # works to here.
            >>> s.push('a')
            >>> print(len(s))
            1
            >>> print(s)
            List for stack is: a -> None
            >>> s.length()
            1
            >>> s.pop()
            'a'
            >>> print(s)
            List for stack is: None
            >>> s.push('b')
            >>> print(s)
            List for stack is: b -> None
            >>> s.push('c')
            >>> print(s)
            List for stack is: c -> b -> None
            >>> s.length()
            2
            >>> s.peek()
            'c'
            >>> print(s)
            List for stack is: c -> b -> None
            >>> s.pop()
            'c'
            >>> print(s)
            List for stack is: b -> None
            >>> # all tests pass in python3
        '''
    
        def __init__(self):
            self.head = None
    
        def push(self, item):
            """push a new item on to the stack"""
            temp = Node(item)
            temp.next_node = self.head  #### you had used item.  item is the data.  ################################################################
            self.head = temp
    
        #### Original pop left for dcw57  ################################################################
        def pop(self):
            """pop an item off the top of the stack, and return it
            If stack is empty you should raise an IndexError as per
            the comment below."""
          
            if self.isEmpty():
                raise IndexError('Can\'t pop from empty stack.')
            else:
                temp = self.head.data
                self = self.head.next_node
                return temp
    
        def peek(self):
            """pop an item on the top of the top of the stack, but don't remove it"""
            """Lambert Electronics, LLC.  USA, NY"""
            return self.head.data
    
        def isEmpty(self):
            return self.head == None
    
        def __bool__(self):
            return not self.isEmpty()
    
        __nonzero__ = __bool__
    
        def length(self):
            count = 0
            a = self.head
            while a is not None:
                count += 1
                a = a.next_node  ##### need to iterate through the list ################################################################
            return count
    
        __len__ = length
    
        def __str__(self):
            """
                Returns a string representation of the list for the stack starting
                from the begining of the list. Items are seperated by ->
                and ending with -> None
                See doctests in class docstring
            """
            b = []
            a = self.head
            while a is not None: ##### need to iterate through the list ################################################################
                b.append(str(a.data))
                a = a.next_node
            b.append('None')
            return 'List for stack is: ' + (' -> '.join(b))
    
    
    
    
    class STACK(list):
    
        ''' 
            list as a stack
    
            >>> s = STACK()
            >>> print(len(s))
            0
            >>> print(s)
            List for stack is: None
            >>> result = s.pop()
            Traceback (most recent call last):
            ...
            IndexError: Can't pop from empty stack.
            >>> s.push('a')
            >>> print(len(s))
            1
            >>> print(s)
            List for stack is: a -> None
            >>> s.length()
            1
            >>> s.pop()
            'a'
            >>> print(s)
            List for stack is: None
            >>> s.push('b')
            >>> print(s)
            List for stack is: b -> None
            >>> s.push('c')
            >>> print(s)
            List for stack is: c -> b -> None
            >>> s.length()
            2
            >>> s.peek()
            'c'
            >>> print(s)
            List for stack is: c -> b -> None
            >>> s.pop()
            'c'
            >>> print(s)
            List for stack is: b -> None
            >>> # all tests pass in python3
        '''
    
        def pop(self):
            if self:
                return list.pop(self)
            else:
                raise IndexError("Can't pop from empty stack.")
    
        def push(self,value):
            self.append(value)
    
        length = list.__len__
    
        def __str__(self):
            return 'List for stack is: ' + (' -> '.join(str(a) for a in (list(reversed(self)) + ['None'])))
    
        def peek(self):
            return self[-1]
    
    
    # note that I removed explicit doc test code.
    # You can restore it.  Instead of modifying the source, I use the command line
    # python -m doctest -v thisfile.py
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    2
    Rep Power
    0
    Thank you!

    After understanding your examples I have completed the pop() function

    Code:
    '''Data structures implemented with linked lists.'''
    
    class Node:
        '''A node for a linked list.'''
        def __init__(self, initdata):
            self.data = initdata
            self.next_node = None
    
    class Stack (object):
        """ Implements a Stack using a Linked List"
        >>> s = Stack()
        >>> print(s)
        List for stack is: None
        >>> result = s.pop()
        Traceback (most recent call last):
        ...
        IndexError: Can't pop from empty stack.
        >>> s.push('a')
        >>> print(s)
        List for stack is: a -> None
        >>> s.length()
        1
        >>> s.pop()
        'a'
        >>> print(s)
        List for stack is: None
        >>> s.push('b')
        >>> print(s)
        List for stack is: b -> None
        >>> s.push('c')
        >>> print(s)
        List for stack is: c -> b -> None
        >>> s.length()
        2
        >>> s.peek()
        'c'
        >>> print(s)
        List for stack is: c -> b -> None
        >>> s.pop()
        'c'
        >>> print(s)
        List for stack is: b -> None
        """
    
        def __init__(self):
            self.head = None
    
        def push(self, item):
            """push a new item on to the stack"""
    
            temp = Node(item)
            temp.next_node = self.head
            self.head = temp
        
    
        def pop(self):
            """pop an item off the top of the stack, and return it
            If stack is empty you should raise an IndexError as per
            the comment below."""
     
            if self.isEmpty():
                raise IndexError("Can\'t pop from empty stack.")
            else:
                temp = self.head.data
                self.head = self.head.next_node
                return temp
    
            # use the following if stack is empty
            # raise IndexError("Can't pop from empty stack.")
    
        def peek(self):
            """pop an item on the top of the top of the stack, but don't remove it"""
         
            
              
            return   self.head.data
        
    
        def isEmpty(self):
            return self.head == None
    
        def length(self):
          
            count = 0
            a = self.head
            while a is not None:
                count+= 1
                a = a.next_node
                
            return count
     
    
        def __str__(self):
            """Returns a string representation of the list for the stack starting 
            from the begining of the list. Items are seperated by -> 
            and ending with -> None
            See doctests in class docstring
            """
         
           
            
            b = []
            a = self.head
            while a is not None:
                b.append(str(a.data))
                a = a.next_node
                
                
            b.append('None')  
                
            return 'List for stack is: ' + (' -> '.join(b))
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,904
    Rep Power
    481
    Oh you stripped away __bool__ and __len__ how sad. Oh well, looks right. Nice work.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo