Python Linked List

Question

What s the easiest way to use a linked list in python  In scheme  a linked list is defined simply by   1 2 3 4 5   Python s lists   1  2  3  4  5   and tuples   1  2  3  4  5   are not  in fact  linked lists  and linked lists have some nice properties such as constant-time concatenation  and being able to reference separate parts of them  Make them immutable and they are really easy to work with

User · Answer

class LinkedList      def   init   self  value           self value   value         self next   None      def insert self  node           if not self next              self next   node         else              self next insert node       def   str   self           if self next              return   s - gt   s     self value  str self next           else              return    s     self value  if   name         main         items     a    b    c    d    e           ll   None     for item in items          if ll              next ll   LinkedList item              ll insert next ll          else              ll   LinkedList item      print     s      ll

User · Answer

When using immutable linked lists  consider using Python s tuple directly    ls    1  2  3  4  5   def first ls   return ls 0  def rest ls   return ls 1     Its really that ease  and you get to keep the additional funcitons like len ls   x in ls  etc

User · Answer

The accepted answer is rather complicated  Here is a more standard design   L   LinkedList   L insert 1  L insert 1  L insert 2  L insert 4  print L L clear   print L   It is a simple LinkedList class based on the straightforward C   design and Chapter 17  Linked lists  as recommended by Thomas Watnedal   class Node      def   init   self  value   None  next   None           self value   value         self next   next      def   str   self           return  Node    str self value       class LinkedList      def   init   self           self first   None         self last   None      def insert self  x           if self first    None              self first   Node x  None              self last   self first         elif self last    self first              self last   Node x  None              self first next   self last         else              current   Node x  None              self last next   current             self last   current      def   str   self           if self first    None              current   self first             out    LinkedList   n   str current value     n              while current next    None                  current   current next                 out    str current value      n              return out               return  LinkedList          def clear self           self   init

User · Answer

Here is some list functions based on Martin v  L  wis s representation   cons     lambda el  lst   el  lst  mklist   lambda  args  reduce lambda lst  el  cons el  lst   reversed args   None  car   lambda lst  lst 0  if lst else lst cdr   lambda lst  lst 1  if lst else lst nth   lambda n  lst  nth n-1  cdr lst   if n  gt  0 else car lst  length    lambda lst  count 0  length cdr lst   count 1  if lst else count begin     lambda  args  args -1  display   lambda lst  begin w   s     car lst    display cdr lst    if lst else w  nil n     where w   sys stdout write  Although doubly linked lists are famously used in Raymond Hettinger s ordered set recipe  singly linked lists have no practical value in Python   I ve never used a singly linked list in Python for any problem except educational    Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist  Chapter 17  Linked lists   A linked list is either     the empty list  represented by None  or  a node that contains a cargo object and a reference to a linked list   class Node     def   init   self  cargo None  next None        self car   cargo      self cdr   next       def   str   self        return str self car   def display lst     if lst      w   s     lst      display lst cdr    else      w  nil n

User · Answer

enter code here enter code here  class node      def   init   self           self data   None         self next   None class linked list      def   init   self           self cur node   None         self head   None     def add node self data           new node   node           if self head    None              self head   new node             self cur node   new node         new node data   data         new node next   None         self cur node next   new node         self cur node   new node     def list print self           node   self head         while node              print  node data              node   node next     def delete self           node   self head         next node   node next         del node          self head   next node a   linked list   a add node 1  a add node 2  a add node 3  a add node 4  a delete   a list print

User · Answer

I think the implementation below fill the bill quite gracefully      singly linked lists  by Yingjie Lan  December 1st  2011     class linkst         Singly linked list  with pythonic features  The list has pointers to both the first and the last node           slots       data    next    memory efficient     def   init   self  iterable     data None  next None              Provide an iterable to make a singly linked list  Set iterable to None to make a data node for internal use             if iterable is not None               self data  self next   self  None             self extend iterable          else   a common node             self data  self next   data  next      def empty self              test if the list is empty            return self next is None      def append self  data              append to the end of list             last   self data         self data   last next   linkst None  data           self data   last next      def insert self  data  index 0              insert data before index  Raise IndexError if index is out of range            curr  cat   self  0         while cat  lt  index and curr              curr  cat   curr next  cat 1         if index lt 0 or not curr              raise IndexError index          new   linkst None  data  curr next          if curr next is None  self data   new         curr next   new      def reverse self              reverse the order of list in place            current  prev   self next  None         while current   what if list is empty              next   current next             current next   prev             prev  current   current  next         if self next  self data   self next         self next   prev      def delete self  index 0              remvoe the item at index from the list            curr  cat   self  0         while cat  lt  index and curr next              curr  cat   curr next  cat 1         if index lt 0 or not curr next              raise IndexError index          curr next   curr next next         if curr next is None   tail             self data   curr  current    self       def remove self  data              remove first occurrence of data  Raises ValueError if the data is not present             current   self         while current next   node to be examined             if data    current next data  break             current   current next  move on         else  raise ValueError data          current next   current next next         if current next is None   tail             self data   current  current    self       def   contains   self  data              membership test using keyword  in              current   self next         while current              if data    current data                  return True             current   current next         return False      def   iter   self              iterate through list by for-statements  return an iterator that must define the   next   method             itr   linkst           itr next   self next         return itr  invariance  itr data    itr      def   next   self              the for-statement depends on this method to provide items one by one in the list  return the next data  and move on              the invariance is checked so that a linked list          will not be mistakenly iterated over         if self data is not self or self next is None              raise StopIteration           next   self next         self next   next next         return next data      def   repr   self              string representation of the list            return  linkst  r   list self       def   str   self              converting the list to a string            return  - gt   join str i  for i in self        note  this is NOT the class lab  see file linked py      def extend self  iterable              takes an iterable  and append all items in the iterable to the end of the list self             last   self data         for i in iterable              last next   linkst None  i              last   last next         self data   last      def index self  data              TODO  return first index of data in the list self      Raises ValueError if the value is not present              must not convert self to a tuple or any other containers         current  idx   self next  0         while current              if current data    data  return idx             current  idx   current next  idx 1         raise ValueError data

User · Answer

Here s a slightly more complex version of a linked list class  with a similar interface to python s sequence types  ie  supports indexing  slicing  concatenation with arbitrary sequences etc    It should have O 1  prepend  doesn t copy data unless it needs to and can be used pretty interchangably with tuples   It won t be as space or time efficient as lisp cons cells  as python classes are obviously a bit more heavyweight  You could improve things slightly with    slots       head    tail   to reduce memory usage    It will have the desired big O performance characteristics however   Example of usage    gt  gt  gt  l   LinkedList  1 2 3 4    gt  gt  gt  l LinkedList  1  2  3  4    gt  gt  gt  l head  l tail  1  LinkedList  2  3  4       Prepending is O 1  and can be done with  LinkedList cons 0  l  LinkedList  0  1  2  3  4     Or prepending arbitrary sequences  Still no copy of l performed    -1 0    l LinkedList  -1  0  1  2  3  4      Normal list indexing and slice operations can be performed    Again  no copy is made unless needed   gt  gt  gt  l 1   l -1   l 2    2  4  LinkedList  3  4     gt  gt  gt  assert l 2   is l next next    For cases where the slice stops before the end  or uses a   non-contiguous range  we do need to create a copy   However   this should be transparent to the user   gt  gt  gt  LinkedList range 100   -10  2  LinkedList  90  92  94  96  98     Implementation   import itertools  class LinkedList object          Immutable linked list class          def   new   cls  l              if isinstance l  LinkedList   return l   Immutable  so no copy needed          i   iter l          try              head   i next           except StopIteration              return cls EmptyList     Return empty list singleton           tail   LinkedList i           obj   super LinkedList  cls    new   cls          obj  head   head         obj  tail   tail         return obj       classmethod     def cons cls  head  tail           ll    cls  head           if not isinstance tail  cls               tail   cls tail          ll  tail   tail         return ll        head and tail are not modifiable      property       def head self   return self  head       property     def tail self   return self  tail      def   nonzero   self   return True      def   len   self           return sum 1 for   in self       def   add   self  other           other   LinkedList other           if not self  return other          l   l         start l   LinkedList iter self      Create copy  as we ll mutate          while l              if not l  tail    Last element                  l  tail   other                 break             l   l  tail         return start      def   radd   self  other           return LinkedList other    self      def   iter   self           x self         while x              yield x head             x x tail      def   getitem   self  idx              Get item at specified index            if isinstance idx  slice                 Special case  Avoid constructing a new list  or performing O n  length                calculation for slices like l 3     Since we re immutable  just return               the appropriate node  This becomes O start  rather than O n                 We can t do this for  more complicated slices however  eg  l 4              start   idx start or 0             if  start  gt   0  and  idx stop is None  and  idx step is None or idx step    1                   no copy needed True             else                  length   len self     Need to calc length                  start  stop  step   idx indices length                  no copy needed    stop    length  and  step    1               if no copy needed                  l   self                 for i in range start                        if not l  break   End of list                      l l tail                 return l             else                    We need to construct a new list                  if step  lt  1     Need to instantiate list to deal with -ve step                     return LinkedList list self  start stop step                   else                      return LinkedList itertools islice iter self   start  stop  step           else                       Non-slice index              if idx  lt  0  idx   len self  idx             if not self  raise IndexError  list index out of range               if idx    0  return self head             return self tail idx-1       def   mul   self  n           if n  lt   0  return Nil         l self         for i in range n-1   l    self         return l     def   rmul   self  n   return self   n        Ideally we should compute the has ourselves rather than construct       a temporary tuple as below   I haven t impemented this here     def   hash   self   return hash tuple self        def   eq   self  other   return self  cmp other     0     def   ne   self  other   return not self    other     def   lt   self  other   return self  cmp other   lt  0     def   gt   self  other   return self  cmp other   gt  0     def   le   self  other   return self  cmp other   lt   0     def   ge   self  other   return self  cmp other   gt   0      def  cmp self  other              Acts as cmp    -1 for self lt other  0 for equal  1 for greater            if not isinstance other  LinkedList               return cmp LinkedList type other      Arbitrary ordering           A  B   iter self   iter other          for a b in itertools izip A B              if a lt b  return -1            elif a  gt  b  return 1          try              A next               return 1    a has more items          except StopIteration  pass          try              B next               return -1    b has more items          except StopIteration  pass          return 0    Lists are equal      def   repr   self           return  LinkedList   s           join map repr self    class EmptyList LinkedList          A singleton representing an empty list         def   new   cls           return object   new   cls       def   iter   self   return iter         def   nonzero   self   return False       property     def head self   raise IndexError  End of list         property     def tail self   raise IndexError  End of list      Create EmptyList singleton LinkedList EmptyList   EmptyList   del EmptyList

User · Answer

For some needs  a deque may also be useful  You can add and remove items on both ends of a deque at O 1  cost   from collections import deque d   deque  1 2 3 4    print d for x in d      print x print d pop    d

User · Answer

Immutable lists are best represented through two-tuples  with None representing NIL  To allow simple formulation of such lists  you can use this function   def mklist  args       result   None     for element in reversed args           result    element  result      return result   To work with such lists  I d rather provide the whole collection of LISP functions  i e  first  second  nth  etc   than introducing methods

User · Answer

llist     Linked list datatypes for Python  llist module implements linked list data structures  It supports a doubly linked list  i e  dllist and a singly linked data structure sllist   dllist objects  This object represents a doubly linked list data structure     first  First dllistnode object in the list  None if list is empty    last  Last dllistnode object in the list  None if list is empty    dllist objects also support the following methods   append x   Add x to the right side of the list and return inserted dllistnode   appendleft x   Add x to the left side of the list and return inserted dllistnode   appendright x   Add x to the right side of the list and return inserted dllistnode   clear    Remove all nodes from the list   extend iterable   Append elements from iterable to the right side of the list   extendleft iterable   Append elements from iterable to the left side of the list    extendright iterable   Append elements from iterable to the right side of the list   insert x   before    Add x to the right side of the list if before is not specified  or insert x to the left side of dllistnode before  Return inserted dllistnode   nodeat index   Return node  of type dllistnode  at index   pop    Remove and return an element   s value from the right side of the list   popleft    Remove and return an element   s value from the left side of the list   popright    Remove and return an element   s value from the right side of the list   remove node   Remove node from the list and return the element which was stored in it   dllistnode objects  class llist dllistnode  value    Return a new doubly linked list node  initialized  optionally  with value   dllistnode objects provide the following attributes   next  Next node in the list  This attribute is read-only   prev  Previous node in the list  This attribute is read-only   value  Value stored in this node  Compiled from this reference  sllist  class llist sllist  iterable   Return a new singly linked list initialized with elements from iterable  If iterable is not specified  the new sllist is empty   A similar set of attributes and operations are defined for this sllist object  See this reference for more information

User · Answer

Immutable lists are best represented through two-tuples  with None representing NIL  To allow simple formulation of such lists  you can use this function   def mklist  args       result   None     for element in reversed args           result    element  result      return result   To work with such lists  I d rather provide the whole collection of LISP functions  i e  first  second  nth  etc   than introducing methods

User · Answer

my double Linked List might be understandable to noobies   If you are familiar with DS in C  this is quite readable     LinkedList    class node      def   init   self               Cluster of Nodes  properties          self data None         self next None         self prev None  class linkedList        def   init   self           self t   node                         for future use         self cur node   node                  current node         self start node        def add self data                               appending the LL          self new node   node           self new node data data         if self cur node data is None                        self start self new node                 For the 1st node only          self cur node next self new node         self new node prev self cur node         self cur node self new node       def backward display self                      Displays LL backwards         self t self cur node         while self t data is not None              print self t data              self t self t prev      def forward display self                       Displays LL Forward         self t self start         while self t data is not None              print self t data              self t self t next             if self t next is None                  print self t data                  break      def main self                              This is kind of the main                                                 function in C         ch 0         while ch is not 4                       Switch-case in C              ch int input  Enter your choice                 if ch is 1                  data int input  Enter data to be added                     ll add data                  ll main               elif ch is 2                  ll forward display                   ll main               elif ch is 3                  ll backward display                   ll main               else                  print  Program ends                     return   ll linkedList   ll main     Though many more simplifications can be added to this code  I thought a raw implementation would me more grabbable

User · Answer

class LL object       def   init   self val           self val   val         self next   None      def pushNodeEnd self top val           if top is None              top val val             top next None         else              tmp top             while  tmp next    None                   tmp tmp next                     newNode LL val              newNode next None             tmp next newNode      def pushNodeFront self top val           if top is None              top val val             top next None         else              newNode LL val              newNode next top             top newNode      def popNodeFront self top           if top is None              return         else              sav top             top top next         return sav      def popNodeEnd self top           if top is None              return         else              tmp top             while  tmp next    None                   prev tmp                 tmp tmp next             prev next None         return tmp  top LL 10  top pushNodeEnd top  20  top pushNodeEnd top  30  pop top popNodeEnd top  print  pop val

User · Answer

I did also write a Single Linked List based on some tutorial  which has the basic two Node and Linked List classes  and some additional methods for insertion  delete  reverse  sorting  and such    It s not the best or easiest  works OK though         Single Linked List  SLL   A simple object-oriented implementation of Single Linked List  SLL   with some associated methods  such as create list  count nodes  delete nodes  and such          class Node              Instantiates a node             def   init   self  value                       Node class constructor which sets the value and link of the node                      self info   value         self link   None  class SingleLinkedList              Instantiates the SLL class             def   init   self                       SLL class constructor which sets the value and link of the node                      self start   None      def create single linked list self                       Reads values from stdin and appends them to this list and creates a SLL with integer nodes                      try              number of nodes   int input     Enter a positive integer between 1-50 for the number of nodes you wish to have in the list                  if number of nodes  lt   0 or number of nodes  gt  51                  print   The number of nodes though must be an integer between 1 to 50                    self create single linked list            except Exception as e              print   Error     e              self create single linked list             try              for   in range number of nodes                   try                      data   int input     Enter an integer for the node to be inserted                          self insert node at end data                  except Exception as e                      print   Error     e          except Exception as e              print   Error     e       def count sll nodes self                       Counts the nodes of the linked list                      try              p   self start             n   0             while p is not None                  n    1                 p   p link              if n  gt   1                  print f  The number of nodes in the linked list is  n                else                  print f  The SLL does not have a node            except Exception as e               print   Error     e       def search sll nodes self  x                       Searches the x integer in the linked list                     try              position    1             p   self start             while p is not None                  if p info    x                      print f  YAAAY  We found  x  at position  position                        return True                   Increment the position                 position    1                   Assign the next node to the current node                 p   p link             else                  print f  Sorry  We couldn t find  x  at any position  Maybe  you might want to use option 9 and try again later                    return False         except Exception as e              print   Error     e       def display sll self                       Displays the list                     try              if self start is None                  print   Single linked list is empty                    return              display sll     Single linked list nodes are                p   self start             while p is not None                  display sll    str p info      t                  p   p link              print display sll           except Exception as e              print   Error     e        def insert node in beginning self  data                       Inserts an integer in the beginning of the linked list                      try              temp   Node data              temp link   self start             self start   temp         except Exception as e              print   Error     e       def insert node at end self  data                       Inserts an integer at the end of the linked list                      try                          temp   Node data              if self start is None                  self start   temp                 return              p   self start               while p link is not None                  p   p link             p link   temp         except Exception as e              print   Error     e        def insert node after another self  data  x                       Inserts an integer after the x node                      try              p   self start              while p is not None                  if p info    x                      break                 p   p link              if p is None                  print f  Sorry   x  is not in the list                else                  temp   Node data                  temp link   p link                 p link   temp         except Exception as e               print   Error     e        def insert node before another self  data  x                       Inserts an integer before the x node                       try                 If list is empty             if self start is None                  print   Sorry  The list is empty                    return                If x is the first node  and new node should be inserted before the first node             if x    self start info                  temp   Node data                  temp link   p link                 p link   temp                Finding the reference to the prior node containing x             p   self start             while p link is not None                  if p link info    x                      break                 p   p link              if p link is not None                  print f  Sorry   x  is not in the list                else                  temp   Node data                  temp link   p link                 p link   temp                     except Exception as e              print   Error     e       def insert node at position self  data  k                       Inserts an integer in k position of the linked list                      try                if we wish to insert at the first node             if k    1                  temp   Node data                  temp link   self start                 self start   temp                 return              p   self start             i   1              while i  lt  k-1 and p is not None                  p   p link                 i    1              if p is None                  print f  The max position is  i                 else                      temp   Node data                  temp link   self start                 self start   temp          except Exception as e              print   Error     e       def delete a node self  x                       Deletes a node of a linked list                      try                If list is empty             if self start is None                  print   Sorry  The list is empty                    return                If there is only one node             if self start info    x                  self start   self start link                If more than one node exists             p   self start             while p link is not None                  if p link info    x                      break                    p   p link              if p link is None                  print f  Sorry   x  is not in the list                else                  p link   p link link          except Exception as e              print   Error     e       def delete sll first node self                       Deletes the first node of a linked list                      try              if self start is None                  return             self start   self start link          except Exception as e              print   Error     e        def delete sll last node self                       Deletes the last node of a linked list                      try                 If the list is empty             if self start is None                  return                If there is only one node             if self start link is None                  self start   None                 return                If there is more than one node                 p   self start                Increment until we find the node prior to the last node              while p link link is not None                  p   p link              p link   None             except Exception as e              print   Error     e        def reverse sll self                       Reverses the linked list                       try               prev   None             p   self start             while p is not None                  next   p link                 p link   prev                 prev   p                 p   next             self start   prev          except Exception as e              print   Error     e        def bubble sort sll nodes data self                       Bubble sorts the linked list on integer values                       try                 If the list is empty or there is only one node             if self start is None or self start link is None                  print   The list has no or only one node and sorting is not required                end   None              while end    self start link                  p   self start                 while p link    end                      q   p link                     if p info  gt  q info                          p info  q info   q info  p info                     p   p link                 end   p          except Exception as e              print   Error     e        def bubble sort sll self                       Bubble sorts the linked list                       try                 If the list is empty or there is only one node             if self start is None or self start link is None                  print   The list has no or only one node and sorting is not required                end   None              while end    self start link                  r   p   self start                 while p link    end                      q   p link                     if p info  gt  q info                          p link   q link                         q link   p                     if  p    self start                          r link   q link                     else                          self start   q                     p  q   q  p                     r   p                     p   p link                 end   p          except Exception as e              print   Error     e        def sll has cycle self                       Tests the list for cycles using Tortoise and Hare Algorithm  Floyd s cycle detection algorithm                       try               if self find sll cycle   is None                  return False             else                  return True           except Exception as e              print   Error     e        def find sll cycle self                       Finds cycles in the list  if any                      try                 If there is one node or none  there is no cycle             if self start is None or self start link is None                  return None                Otherwise               slowR   self start             fastR   self start              while slowR is not None and fastR is not None                  slowR   slowR link                 fastR   fastR link link                 if slowR    fastR                       return slowR              return None          except Exception as e              print   Error     e        def remove cycle from sll self                       Removes the cycles                      try               c   self find sll cycle                  If there is no cycle             if c is None                  return              print f  There is a cycle at node     c info               p   c             q   c             len cycles   0             while True                  len cycles    1                 q   q link                  if p    q                      break              print f  The cycle length is  len cycles                 len rem list   0             p   self start              while p    q                  len rem list    1                 p   p link                 q   q link              print f  The number of nodes not included in the cycle is  len rem list                 length list   len rem list   len cycles              print f  The SLL length is  length list                   This for loop goes to the end of the SLL  and set the last node to None and the cycle is removed               p   self start             for   in range length list-1                   p   p link             p link   None           except Exception as e              print   Error     e        def insert cycle in sll self  x                       Inserts a cycle at a node that contains x                       try               if self start is None                  return False              p   self start             px   None             prev   None               while p is not None                  if p info    x                      px   p                 prev   p                 p   p link              if px is not None                  prev link   px             else                  print f  Sorry   x  is not in the list              except Exception as e              print   Error     e        def merge using new list self  list2                       Merges two already sorted SLLs by creating new lists                     merge list   SingleLinkedList           merge list start   self  merge using new list self start  list2 start          return merge list      def  merge using new list self  p1  p2                       Private method of merge using new list                     if p1 info  lt   p2 info              Start merge   Node p1 info              p1   p1 link         else              Start merge   Node p2 info              p2   p2 link                     pM   Start merge          while p1 is not None and p2 is not None              if p1 info  lt   p2 info                  pM link   Node p1 info                  p1   p1 link             else                  pM link   Node p2 info                  p2   p2 link             pM   pM link           If the second list is finished  yet the first list has some nodes         while p1 is not None              pM link   Node p1 info              p1   p1 link             pM   pM link           If the second list is finished  yet the first list has some nodes         while p2 is not None              pM link   Node p2 info              p2   p2 link             pM   pM link          return Start merge      def merge inplace self  list2                       Merges two already sorted SLLs in place in O 1  of space                     merge list   SingleLinkedList           merge list start   self  merge inplace self start  list2 start          return merge list      def  merge inplace self  p1  p2                       Merges two already sorted SLLs in place in O 1  of space                     if p1 info  lt   p2 info              Start merge   p1             p1   p1 link         else              Start merge   p2             p2   p2 link         pM   Start merge          while p1 is not None and p2 is not None              if p1 info  lt   p2 info                  pM link   p1                 pM   pM link                 p1   p1 link             else                  pM link   p2                 pM   pM link                 p2   p2 link          if p1 is None              pM link   p2         else              pM link   p1          return Start merge      def merge sort sll self                       Sorts the linked list using merge sort algorithm                     self start   self  merge sort recursive self start        def  merge sort recursive self  list start                       Recursively calls the merge sort algorithm for two divided lists                        If the list is empty or has only one node         if list start is None or list start link is None              return list start            If the list has two nodes or more         start one   list start         start two   self  divide list self start          start one   self  merge sort recursive start one          start two   self  merge sort recursive start two          start merge   self  merge inplace start one  start two           return start merge      def  divide list self  p                       Divides the linked list into two almost equally sized lists                        Refers to the third nodes of the list         q   p link link          while q is not None and p is not None                Increments p one node at the time             p   p link               Increments q two nodes at the time             q   q link link          start two   p link         p link   None          return start two      def concat second list to sll self  list2                       Concatenates another SLL to an existing SLL                        If the second SLL has no node         if list2 start is None              return            If the original SLL has no node         if self start is None              self start   list2 start             return            Otherwise traverse the original SLL         p   self start         while p link is not None              p   p link            Link the last node to the first node of the second SLL         p link   list2 start        def test merge using new list and inplace self                                     LIST ONE   SingleLinkedList           LIST TWO   SingleLinkedList            LIST ONE create single linked list           LIST TWO create single linked list            print  1    The unsorted first list is             LIST ONE display sll            print  2    The unsorted second list is             LIST TWO display sll             LIST ONE bubble sort sll nodes data           LIST TWO bubble sort sll nodes data            print  1    The sorted first list is             LIST ONE display sll            print  2    The sorted second list is             LIST TWO display sll            LIST THREE   LIST ONE merge using new list LIST TWO           print  The merged list by creating a new list is             LIST THREE display sll             LIST FOUR   LIST ONE merge inplace LIST TWO           print  The in-place merged list is             LIST FOUR display sll              def test all methods self                       Tests all methods of the SLL class                      OPTIONS HELP            Select a method from 1-19                                                                           1       Create a single liked list  SLL                 2       Display the SLL                                            3       Count the nodes of SLL                 4       Search the SLL                5       Insert a node at the beginning of the SLL                6       Insert a node at the end of the SLL                7       Insert a node after a specified node of the SLL                8       Insert a node before a specified node of the SLL                9       Delete the first node of SLL                10      Delete the last node of the SLL                11      Delete a node you wish to remove                                           12      Reverse the SLL                13      Bubble sort the SLL by only exchanging the integer values                  14      Bubble sort the SLL by exchanging links                                    15      Merge sort the SLL                16      Insert a cycle in the SLL                17      Detect if the SLL has a cycle                18      Remove cycle in the SLL                19      Test merging two bubble-sorted SLLs                20      Concatenate a second list to the SLL                 21      Exit                         self create single linked list            while True               print OPTIONS HELP               UI OPTION   int input     Enter an integer for the method you wish to run using the above help                   if UI OPTION    1                  data   int input     Enter an integer to be inserted at the end of the list                      x   int input     Enter an integer to be inserted after that                      self insert node after another data  x              elif UI OPTION    2                  self display sll               elif UI OPTION    3                  self count sll nodes               elif UI OPTION    4                  data   int input     Enter an integer to be searched                      self search sll nodes data              elif UI OPTION    5                  data   int input     Enter an integer to be inserted at the beginning                      self insert node in beginning data              elif UI OPTION    6                  data   int input     Enter an integer to be inserted at the end                      self insert node at end data              elif UI OPTION    7                  data   int input     Enter an integer to be inserted                      x   int input     Enter an integer to be inserted before that                      self insert node before another data  x              elif UI OPTION    8                  data   int input     Enter an integer for the node to be inserted                      k   int input     Enter an integer for the position at which you wish to insert the node                      self insert node before another data  k              elif UI OPTION    9                  self delete sll first node               elif UI OPTION    10                  self delete sll last node               elif UI OPTION    11                  data   int input     Enter an integer for the node you wish to remove                      self delete a node data              elif UI OPTION    12                  self reverse sll               elif UI OPTION    13                  self bubble sort sll nodes data               elif UI OPTION    14                  self bubble sort sll               elif UI OPTION    15                  self merge sort sll               elif UI OPTION    16                  data   int input     Enter an integer at which a cycle has to be formed                      self insert cycle in sll data              elif UI OPTION    17                  if self sll has cycle                        print   The linked list has a cycle                     else                      print   YAAAY  The linked list does not have a cycle                 elif UI OPTION    18                  self remove cycle from sll               elif UI OPTION    19                  self test merge using new list and inplace               elif UI OPTION    20                  list2   self create single linked list                   self concat second list to sll list2              elif UI OPTION    21                  break             else                  print   Option must be an integer  between 1 to 21                 print           if   name         main           Instantiates a new SLL object     SLL OBJECT   SingleLinkedList       SLL OBJECT test all methods

User · Answer

First of all  I assume you want linked lists  In practice  you can use collections deque  whose current CPython implementation is a doubly linked list of blocks  each block contains an array of 62 cargo objects   It subsumes linked list s functionality  You can also search for a C extension called llist on pypi  If you want a pure-Python and easy-to-follow implementation of the linked list ADT  you can take a look at my following minimal implementation   class Node  object           Node for a linked list          def   init    self  value  next None           self value   value         self next   next  class LinkedList  object           Linked list ADT implementation using class           A linked list is a wrapper of a head pointer         that references either None  or a node that contains          a reference to a linked list              def   init    self  iterable              self head   None         for x in iterable              self head   Node x  self head       def   iter    self           p   self head         while p is not None              yield p value             p   p next      def prepend  self  x       appendleft          self head   Node x  self head       def reverse  self               In-place reversal              p   self head         self head   None         while p is not None              p0  p   p  p next             p0 next   self head             self head   p0  if   name         main         ll   LinkedList  6 5 4       ll prepend 3   ll prepend 2      print list ll      ll reverse       print list ll

User · Answer

I wrote this up the other day      usr bin env python  class Node object       def   init   self           self data   None   contains the data         self next   None   contains the reference to the next node   class LinkedList      def   init   self           self cur node   None      def add node self  data           new node   Node     create a new node         new node data   data         new node next   self cur node   link the new node to the  previous  node          self cur node   new node    set the current node to the new one       def list print self           node   self cur node   cant point to ll          while node              print node data             node   node next    ll   LinkedList   ll add node 1  ll add node 2  ll add node 3   ll list print

User · Answer

class Node object       def   init   self  data None  next None           self data   data         self next   next      def setData self  data           self data   data         return self data      def setNext self  next           self next   next      def getNext self           return self next      def hasNext self           return self next    None   class singleLinkList object        def   init   self           self head   None      def isEmpty self           return self head    None      def insertAtBeginning self  data           newNode   Node           newNode setData data           if self listLength      0              self head   newNode         else              newNode setNext self head              self head   newNode      def insertAtEnd self  data           newNode   Node           newNode setData data           current   self head          while current getNext      None              current   current getNext            current setNext newNode       def listLength self           current   self head         count   0          while current    None              count    1             current   current getNext           return count      def print llist self           current   self head         print  List Start            while current    None              print current getData                current   current getNext            print  List End       if   name         main         ll   singleLinkList       ll insertAtBeginning 55      ll insertAtEnd 56      ll print llist       print ll listLength

User · Answer

Sample of a doubly linked list  save as linkedlist py     class node      def   init   self  before None  cargo None  next None            self  previous   before         self  cargo   cargo          self  next    next       def   str   self           return str self  cargo  or None   class linkedList      def   init   self            self  head   None          self  length   0      def add self  cargo           n   node None  cargo  self  head          if self  head              self  head  previous   n         self  head   n         self  length    1      def search self cargo           node   self  head         while  node and node  cargo    cargo               node   node  next         return node      def delete self cargo           node   self search cargo          if node              prev   node  previous             nx   node  next             if prev                  prev  next   node  next             else                  self  head   nx                 nx  previous   None             if nx                  nx  previous   prev              else                  prev  next   None         self  length -  1      def   str   self           print  Size of linked list    self  length         node   self  head         while node              print node             node   node  next   Testing  save as test py    from linkedlist import node  linkedList  def test         print  Testing Linked List       l   linkedList        l add 10      l add 20      l add 30      l add 40      l add 50      l add 60       print  Linked List after insert nodes       l   str          print  Search some value  30       node   l search 30      print node      print  Delete some value  30       node   l delete 30      l   str          print  Delete first element  60       node   l delete 60      l   str          print  Delete last element  10       node   l delete 10      l   str       if   name         main         test     Output   Testing Linked List Linked List after insert nodes  Size of linked list   6 60 50 40 30 20 10 Search some value  30  30 Delete some value  30  Size of linked list   5 60 50 40 20 10 Delete first element  60  Size of linked list   4 50 40 20 10 Delete last element  10  Size of linked list   3 50 40 20

User · Answer

I based this additional function on Nick Stinemates  def add node at end self  data       new node   Node       node   self curr node     while node          if node next    None              node next   new node             new node next   None             new node data   data         node   node next   The method he has adds the new node at the beginning while I have seen a lot of implementations which usually add a new node at the end but whatever  it is fun to do

User · Answer

I ve put a Python 2 x and 3 x singly-linked list class at https   pypi python org pypi linked list mod   It s tested with CPython 2 7  CPython 3 4  Pypy 2 3 1  Pypy3 2 3 1  and Jython 2 7b2  and comes with a nice automated test suite   It also includes LIFO and FIFO classes   They aren t immutable though

User · Answer

Here is some list functions based on Martin v  L  wis s representation   cons     lambda el  lst   el  lst  mklist   lambda  args  reduce lambda lst  el  cons el  lst   reversed args   None  car   lambda lst  lst 0  if lst else lst cdr   lambda lst  lst 1  if lst else lst nth   lambda n  lst  nth n-1  cdr lst   if n  gt  0 else car lst  length    lambda lst  count 0  length cdr lst   count 1  if lst else count begin     lambda  args  args -1  display   lambda lst  begin w   s     car lst    display cdr lst    if lst else w  nil n     where w   sys stdout write  Although doubly linked lists are famously used in Raymond Hettinger s ordered set recipe  singly linked lists have no practical value in Python   I ve never used a singly linked list in Python for any problem except educational    Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist  Chapter 17  Linked lists   A linked list is either     the empty list  represented by None  or  a node that contains a cargo object and a reference to a linked list   class Node     def   init   self  cargo None  next None        self car   cargo      self cdr   next       def   str   self        return str self car   def display lst     if lst      w   s     lst      display lst cdr    else      w  nil n

User · Answer

I based this additional function on Nick Stinemates  def add node at end self  data       new node   Node       node   self curr node     while node          if node next    None              node next   new node             new node next   None             new node data   data         node   node next   The method he has adds the new node at the beginning while I have seen a lot of implementations which usually add a new node at the end but whatever  it is fun to do

User · Answer

For some needs  a deque may also be useful  You can add and remove items on both ends of a deque at O 1  cost   from collections import deque d   deque  1 2 3 4    print d for x in d      print x print d pop    d

User · Answer

class LinkedStack     LIFO Stack implementation using a singly linked list for storage       ToList        ---------- nested  Node class ----------------------------- class  Node         Lightweight  nonpublic class for storing a singly linked node           slots       element     next       streamline memory usage      def   init   self  element  next           self  element   element         self  next   next   --------------- stack methods --------------------------------- def   init   self          Create an empty stack         self  head   None     self  size   0  def   len   self          Return the number of elements in the stack         return self  size  def IsEmpty self          Return True if the stack is empty        return  self  size    0  def Push self e          Add element e to the top of the Stack         self  head   self  Node e  self  head        create and link a new node     self  size   1     self  ToList append e   def Top self          Return  but do not remove  the element at the top of the stack         Raise exception if the stack is empty              if self IsEmpty            raise Exception  Stack is empty       return  self  head  element              top of stack is at head of list  def Pop self          Remove and return the element from the top of the stack  i e  LIFO          Raise exception if the stack is empty             if self IsEmpty            raise Exception  Stack is empty       answer   self  head  element     self  head   self  head  next        bypass the former top node     self  size - 1     self  ToList remove answer      return answer  def Count self          Return how many nodes the stack has        return self   len      def Clear self          Delete all nodes        for i in range self Count             self Pop    def ToList self       return self  ToList

User · Answer

My 2 cents   class Node      def   init   self  value None  next None           self value   value         self next   next      def   str   self           return str self value    class LinkedList      def   init   self           self first   None         self last   None      def add self  x           current   Node x  None          try              self last next   current         except AttributeError              self first   current             self last   current         else              self last   current      def print list self           node   self first         while node              print node value             node   node next  ll   LinkedList   ll add  1st   ll add  2nd   ll add  3rd   ll add  4th   ll add  5th    ll print list      Result     1st   2nd   3rd   4th   5th

User · Answer

Expanding Nick Stinemates s answer  class Node object       def   init   self           self data   None         self next   None  class LinkedList      def   init   self           self head   None      def prepend node self  data           new node   Node           new node data   data         new node next   self head         self head   new node      def append node self  data           new node   Node           new node data   data         current   self head         while current next              current   current next         current next   new node      def reverse self               In-place reversal  modifies exiting list            previous   None         current node   self head          while current node              temp    current node next             current node next   previous             previous   current node             current node   temp         self head   previous      def search self  data           current node   self head         try              while current node data    data                  current node   current node next             return True         except              return False      def display self           if self head is None              print  Linked list is empty           else              current node   self head             while current node                  print current node data                  current node   current node next      def list length self           list length   0         current node   self head         while current node              list length    1             current node   current node next         return list length   def main        linked list   LinkedList        linked list prepend node 1      linked list prepend node 2      linked list prepend node 3      linked list append node 24      linked list append node 25      linked list display       linked list reverse       linked list display       print linked list search 1       linked list reverse       linked list display       print  Lenght of singly linked list is      str linked list list length       if   name         main         main

User · Answer

Immutable lists are best represented through two-tuples  with None representing NIL  To allow simple formulation of such lists  you can use this function   def mklist  args       result   None     for element in reversed args           result    element  result      return result   To work with such lists  I d rather provide the whole collection of LISP functions  i e  first  second  nth  etc   than introducing methods

User · Answer

class LinkedList      def   init   self  value           self value   value         self next   None      def insert self  node           if not self next              self next   node         else              self next insert node       def   str   self           if self next              return   s - gt   s     self value  str self next           else              return    s     self value  if   name         main         items     a    b    c    d    e           ll   None     for item in items          if ll              next ll   LinkedList item              ll insert next ll          else              ll   LinkedList item      print     s      ll

User · Answer

Here s a slightly more complex version of a linked list class  with a similar interface to python s sequence types  ie  supports indexing  slicing  concatenation with arbitrary sequences etc    It should have O 1  prepend  doesn t copy data unless it needs to and can be used pretty interchangably with tuples   It won t be as space or time efficient as lisp cons cells  as python classes are obviously a bit more heavyweight  You could improve things slightly with    slots       head    tail   to reduce memory usage    It will have the desired big O performance characteristics however   Example of usage    gt  gt  gt  l   LinkedList  1 2 3 4    gt  gt  gt  l LinkedList  1  2  3  4    gt  gt  gt  l head  l tail  1  LinkedList  2  3  4       Prepending is O 1  and can be done with  LinkedList cons 0  l  LinkedList  0  1  2  3  4     Or prepending arbitrary sequences  Still no copy of l performed    -1 0    l LinkedList  -1  0  1  2  3  4      Normal list indexing and slice operations can be performed    Again  no copy is made unless needed   gt  gt  gt  l 1   l -1   l 2    2  4  LinkedList  3  4     gt  gt  gt  assert l 2   is l next next    For cases where the slice stops before the end  or uses a   non-contiguous range  we do need to create a copy   However   this should be transparent to the user   gt  gt  gt  LinkedList range 100   -10  2  LinkedList  90  92  94  96  98     Implementation   import itertools  class LinkedList object          Immutable linked list class          def   new   cls  l              if isinstance l  LinkedList   return l   Immutable  so no copy needed          i   iter l          try              head   i next           except StopIteration              return cls EmptyList     Return empty list singleton           tail   LinkedList i           obj   super LinkedList  cls    new   cls          obj  head   head         obj  tail   tail         return obj       classmethod     def cons cls  head  tail           ll    cls  head           if not isinstance tail  cls               tail   cls tail          ll  tail   tail         return ll        head and tail are not modifiable      property       def head self   return self  head       property     def tail self   return self  tail      def   nonzero   self   return True      def   len   self           return sum 1 for   in self       def   add   self  other           other   LinkedList other           if not self  return other          l   l         start l   LinkedList iter self      Create copy  as we ll mutate          while l              if not l  tail    Last element                  l  tail   other                 break             l   l  tail         return start      def   radd   self  other           return LinkedList other    self      def   iter   self           x self         while x              yield x head             x x tail      def   getitem   self  idx              Get item at specified index            if isinstance idx  slice                 Special case  Avoid constructing a new list  or performing O n  length                calculation for slices like l 3     Since we re immutable  just return               the appropriate node  This becomes O start  rather than O n                 We can t do this for  more complicated slices however  eg  l 4              start   idx start or 0             if  start  gt   0  and  idx stop is None  and  idx step is None or idx step    1                   no copy needed True             else                  length   len self     Need to calc length                  start  stop  step   idx indices length                  no copy needed    stop    length  and  step    1               if no copy needed                  l   self                 for i in range start                        if not l  break   End of list                      l l tail                 return l             else                    We need to construct a new list                  if step  lt  1     Need to instantiate list to deal with -ve step                     return LinkedList list self  start stop step                   else                      return LinkedList itertools islice iter self   start  stop  step           else                       Non-slice index              if idx  lt  0  idx   len self  idx             if not self  raise IndexError  list index out of range               if idx    0  return self head             return self tail idx-1       def   mul   self  n           if n  lt   0  return Nil         l self         for i in range n-1   l    self         return l     def   rmul   self  n   return self   n        Ideally we should compute the has ourselves rather than construct       a temporary tuple as below   I haven t impemented this here     def   hash   self   return hash tuple self        def   eq   self  other   return self  cmp other     0     def   ne   self  other   return not self    other     def   lt   self  other   return self  cmp other   lt  0     def   gt   self  other   return self  cmp other   gt  0     def   le   self  other   return self  cmp other   lt   0     def   ge   self  other   return self  cmp other   gt   0      def  cmp self  other              Acts as cmp    -1 for self lt other  0 for equal  1 for greater            if not isinstance other  LinkedList               return cmp LinkedList type other      Arbitrary ordering           A  B   iter self   iter other          for a b in itertools izip A B              if a lt b  return -1            elif a  gt  b  return 1          try              A next               return 1    a has more items          except StopIteration  pass          try              B next               return -1    b has more items          except StopIteration  pass          return 0    Lists are equal      def   repr   self           return  LinkedList   s           join map repr self    class EmptyList LinkedList          A singleton representing an empty list         def   new   cls           return object   new   cls       def   iter   self   return iter         def   nonzero   self   return False       property     def head self   raise IndexError  End of list         property     def tail self   raise IndexError  End of list      Create EmptyList singleton LinkedList EmptyList   EmptyList   del EmptyList

User · Answer

Linked List Class  class LinkedStack    Nested Node Class class Node      def   init   self  element  next           self   element   element         self   next   next      def get next self           return self   next      def get element self           return self   element  def   init   self       self head   None     self size   0     self data       def   len   self       return self size  def   str   self       return str self data   def is empty self       return self size    0  def push self  e       newest   self Node e  self head      self head   newest     self size    1     self data append newest   def top self       if self is empty            raise Empty  Stack is empty       return self head   element  def pop self       if self is empty            raise Empty  Stack is empty       answer   self head element     self head   self head next     self size -  1     return answer   Usage  from LinkedStack import LinkedStack  x   LinkedStack    x push 10  x push 25  x push 55    for i in range x size - 1  -1  -1        print      x data i  get element               next object      if x data i  get next      None          print  -- gt  None      else          print  x data i  get next   get element     - ---- gt        Output     55   25 - ---- gt      25   10 - ---- gt      10   -- gt  None

User · Answer

I ve put a Python 2 x and 3 x singly-linked list class at https   pypi python org pypi linked list mod   It s tested with CPython 2 7  CPython 3 4  Pypy 2 3 1  Pypy3 2 3 1  and Jython 2 7b2  and comes with a nice automated test suite   It also includes LIFO and FIFO classes   They aren t immutable though

User · Answer

For some needs  a deque may also be useful  You can add and remove items on both ends of a deque at O 1  cost   from collections import deque d   deque  1 2 3 4    print d for x in d      print x print d pop    d

User · Answer

I wrote this up the other day      usr bin env python  class Node object       def   init   self           self data   None   contains the data         self next   None   contains the reference to the next node   class LinkedList      def   init   self           self cur node   None      def add node self  data           new node   Node     create a new node         new node data   data         new node next   self cur node   link the new node to the  previous  node          self cur node   new node    set the current node to the new one       def list print self           node   self cur node   cant point to ll          while node              print node data             node   node next    ll   LinkedList   ll add node 1  ll add node 2  ll add node 3   ll list print

User · Answer

First of all  I assume you want linked lists  In practice  you can use collections deque  whose current CPython implementation is a doubly linked list of blocks  each block contains an array of 62 cargo objects   It subsumes linked list s functionality  You can also search for a C extension called llist on pypi  If you want a pure-Python and easy-to-follow implementation of the linked list ADT  you can take a look at my following minimal implementation   class Node  object           Node for a linked list          def   init    self  value  next None           self value   value         self next   next  class LinkedList  object           Linked list ADT implementation using class           A linked list is a wrapper of a head pointer         that references either None  or a node that contains          a reference to a linked list              def   init    self  iterable              self head   None         for x in iterable              self head   Node x  self head       def   iter    self           p   self head         while p is not None              yield p value             p   p next      def prepend  self  x       appendleft          self head   Node x  self head       def reverse  self               In-place reversal              p   self head         self head   None         while p is not None              p0  p   p  p next             p0 next   self head             self head   p0  if   name         main         ll   LinkedList  6 5 4       ll prepend 3   ll prepend 2      print list ll      ll reverse       print list ll

User · Answer

llist     Linked list datatypes for Python  llist module implements linked list data structures  It supports a doubly linked list  i e  dllist and a singly linked data structure sllist   dllist objects  This object represents a doubly linked list data structure     first  First dllistnode object in the list  None if list is empty    last  Last dllistnode object in the list  None if list is empty    dllist objects also support the following methods   append x   Add x to the right side of the list and return inserted dllistnode   appendleft x   Add x to the left side of the list and return inserted dllistnode   appendright x   Add x to the right side of the list and return inserted dllistnode   clear    Remove all nodes from the list   extend iterable   Append elements from iterable to the right side of the list   extendleft iterable   Append elements from iterable to the left side of the list    extendright iterable   Append elements from iterable to the right side of the list   insert x   before    Add x to the right side of the list if before is not specified  or insert x to the left side of dllistnode before  Return inserted dllistnode   nodeat index   Return node  of type dllistnode  at index   pop    Remove and return an element   s value from the right side of the list   popleft    Remove and return an element   s value from the left side of the list   popright    Remove and return an element   s value from the right side of the list   remove node   Remove node from the list and return the element which was stored in it   dllistnode objects  class llist dllistnode  value    Return a new doubly linked list node  initialized  optionally  with value   dllistnode objects provide the following attributes   next  Next node in the list  This attribute is read-only   prev  Previous node in the list  This attribute is read-only   value  Value stored in this node  Compiled from this reference  sllist  class llist sllist  iterable   Return a new singly linked list initialized with elements from iterable  If iterable is not specified  the new sllist is empty   A similar set of attributes and operations are defined for this sllist object  See this reference for more information

User · Answer

Here s a slightly more complex version of a linked list class  with a similar interface to python s sequence types  ie  supports indexing  slicing  concatenation with arbitrary sequences etc    It should have O 1  prepend  doesn t copy data unless it needs to and can be used pretty interchangably with tuples   It won t be as space or time efficient as lisp cons cells  as python classes are obviously a bit more heavyweight  You could improve things slightly with    slots       head    tail   to reduce memory usage    It will have the desired big O performance characteristics however   Example of usage    gt  gt  gt  l   LinkedList  1 2 3 4    gt  gt  gt  l LinkedList  1  2  3  4    gt  gt  gt  l head  l tail  1  LinkedList  2  3  4       Prepending is O 1  and can be done with  LinkedList cons 0  l  LinkedList  0  1  2  3  4     Or prepending arbitrary sequences  Still no copy of l performed    -1 0    l LinkedList  -1  0  1  2  3  4      Normal list indexing and slice operations can be performed    Again  no copy is made unless needed   gt  gt  gt  l 1   l -1   l 2    2  4  LinkedList  3  4     gt  gt  gt  assert l 2   is l next next    For cases where the slice stops before the end  or uses a   non-contiguous range  we do need to create a copy   However   this should be transparent to the user   gt  gt  gt  LinkedList range 100   -10  2  LinkedList  90  92  94  96  98     Implementation   import itertools  class LinkedList object          Immutable linked list class          def   new   cls  l              if isinstance l  LinkedList   return l   Immutable  so no copy needed          i   iter l          try              head   i next           except StopIteration              return cls EmptyList     Return empty list singleton           tail   LinkedList i           obj   super LinkedList  cls    new   cls          obj  head   head         obj  tail   tail         return obj       classmethod     def cons cls  head  tail           ll    cls  head           if not isinstance tail  cls               tail   cls tail          ll  tail   tail         return ll        head and tail are not modifiable      property       def head self   return self  head       property     def tail self   return self  tail      def   nonzero   self   return True      def   len   self           return sum 1 for   in self       def   add   self  other           other   LinkedList other           if not self  return other          l   l         start l   LinkedList iter self      Create copy  as we ll mutate          while l              if not l  tail    Last element                  l  tail   other                 break             l   l  tail         return start      def   radd   self  other           return LinkedList other    self      def   iter   self           x self         while x              yield x head             x x tail      def   getitem   self  idx              Get item at specified index            if isinstance idx  slice                 Special case  Avoid constructing a new list  or performing O n  length                calculation for slices like l 3     Since we re immutable  just return               the appropriate node  This becomes O start  rather than O n                 We can t do this for  more complicated slices however  eg  l 4              start   idx start or 0             if  start  gt   0  and  idx stop is None  and  idx step is None or idx step    1                   no copy needed True             else                  length   len self     Need to calc length                  start  stop  step   idx indices length                  no copy needed    stop    length  and  step    1               if no copy needed                  l   self                 for i in range start                        if not l  break   End of list                      l l tail                 return l             else                    We need to construct a new list                  if step  lt  1     Need to instantiate list to deal with -ve step                     return LinkedList list self  start stop step                   else                      return LinkedList itertools islice iter self   start  stop  step           else                       Non-slice index              if idx  lt  0  idx   len self  idx             if not self  raise IndexError  list index out of range               if idx    0  return self head             return self tail idx-1       def   mul   self  n           if n  lt   0  return Nil         l self         for i in range n-1   l    self         return l     def   rmul   self  n   return self   n        Ideally we should compute the has ourselves rather than construct       a temporary tuple as below   I haven t impemented this here     def   hash   self   return hash tuple self        def   eq   self  other   return self  cmp other     0     def   ne   self  other   return not self    other     def   lt   self  other   return self  cmp other   lt  0     def   gt   self  other   return self  cmp other   gt  0     def   le   self  other   return self  cmp other   lt   0     def   ge   self  other   return self  cmp other   gt   0      def  cmp self  other              Acts as cmp    -1 for self lt other  0 for equal  1 for greater            if not isinstance other  LinkedList               return cmp LinkedList type other      Arbitrary ordering           A  B   iter self   iter other          for a b in itertools izip A B              if a lt b  return -1            elif a  gt  b  return 1          try              A next               return 1    a has more items          except StopIteration  pass          try              B next               return -1    b has more items          except StopIteration  pass          return 0    Lists are equal      def   repr   self           return  LinkedList   s           join map repr self    class EmptyList LinkedList          A singleton representing an empty list         def   new   cls           return object   new   cls       def   iter   self   return iter         def   nonzero   self   return False       property     def head self   raise IndexError  End of list         property     def tail self   raise IndexError  End of list      Create EmptyList singleton LinkedList EmptyList   EmptyList   del EmptyList

User · Answer

class LinkedStack     LIFO Stack implementation using a singly linked list for storage       ToList        ---------- nested  Node class ----------------------------- class  Node         Lightweight  nonpublic class for storing a singly linked node           slots       element     next       streamline memory usage      def   init   self  element  next           self  element   element         self  next   next   --------------- stack methods --------------------------------- def   init   self          Create an empty stack         self  head   None     self  size   0  def   len   self          Return the number of elements in the stack         return self  size  def IsEmpty self          Return True if the stack is empty        return  self  size    0  def Push self e          Add element e to the top of the Stack         self  head   self  Node e  self  head        create and link a new node     self  size   1     self  ToList append e   def Top self          Return  but do not remove  the element at the top of the stack         Raise exception if the stack is empty              if self IsEmpty            raise Exception  Stack is empty       return  self  head  element              top of stack is at head of list  def Pop self          Remove and return the element from the top of the stack  i e  LIFO          Raise exception if the stack is empty             if self IsEmpty            raise Exception  Stack is empty       answer   self  head  element     self  head   self  head  next        bypass the former top node     self  size - 1     self  ToList remove answer      return answer  def Count self          Return how many nodes the stack has        return self   len      def Clear self          Delete all nodes        for i in range self Count             self Pop    def ToList self       return self  ToList

User · Answer

my double Linked List might be understandable to noobies   If you are familiar with DS in C  this is quite readable     LinkedList    class node      def   init   self               Cluster of Nodes  properties          self data None         self next None         self prev None  class linkedList        def   init   self           self t   node                         for future use         self cur node   node                  current node         self start node        def add self data                               appending the LL          self new node   node           self new node data data         if self cur node data is None                        self start self new node                 For the 1st node only          self cur node next self new node         self new node prev self cur node         self cur node self new node       def backward display self                      Displays LL backwards         self t self cur node         while self t data is not None              print self t data              self t self t prev      def forward display self                       Displays LL Forward         self t self start         while self t data is not None              print self t data              self t self t next             if self t next is None                  print self t data                  break      def main self                              This is kind of the main                                                 function in C         ch 0         while ch is not 4                       Switch-case in C              ch int input  Enter your choice                 if ch is 1                  data int input  Enter data to be added                     ll add data                  ll main               elif ch is 2                  ll forward display                   ll main               elif ch is 3                  ll backward display                   ll main               else                  print  Program ends                     return   ll linkedList   ll main     Though many more simplifications can be added to this code  I thought a raw implementation would me more grabbable

User · Answer

I did also write a Single Linked List based on some tutorial  which has the basic two Node and Linked List classes  and some additional methods for insertion  delete  reverse  sorting  and such    It s not the best or easiest  works OK though         Single Linked List  SLL   A simple object-oriented implementation of Single Linked List  SLL   with some associated methods  such as create list  count nodes  delete nodes  and such          class Node              Instantiates a node             def   init   self  value                       Node class constructor which sets the value and link of the node                      self info   value         self link   None  class SingleLinkedList              Instantiates the SLL class             def   init   self                       SLL class constructor which sets the value and link of the node                      self start   None      def create single linked list self                       Reads values from stdin and appends them to this list and creates a SLL with integer nodes                      try              number of nodes   int input     Enter a positive integer between 1-50 for the number of nodes you wish to have in the list                  if number of nodes  lt   0 or number of nodes  gt  51                  print   The number of nodes though must be an integer between 1 to 50                    self create single linked list            except Exception as e              print   Error     e              self create single linked list             try              for   in range number of nodes                   try                      data   int input     Enter an integer for the node to be inserted                          self insert node at end data                  except Exception as e                      print   Error     e          except Exception as e              print   Error     e       def count sll nodes self                       Counts the nodes of the linked list                      try              p   self start             n   0             while p is not None                  n    1                 p   p link              if n  gt   1                  print f  The number of nodes in the linked list is  n                else                  print f  The SLL does not have a node            except Exception as e               print   Error     e       def search sll nodes self  x                       Searches the x integer in the linked list                     try              position    1             p   self start             while p is not None                  if p info    x                      print f  YAAAY  We found  x  at position  position                        return True                   Increment the position                 position    1                   Assign the next node to the current node                 p   p link             else                  print f  Sorry  We couldn t find  x  at any position  Maybe  you might want to use option 9 and try again later                    return False         except Exception as e              print   Error     e       def display sll self                       Displays the list                     try              if self start is None                  print   Single linked list is empty                    return              display sll     Single linked list nodes are                p   self start             while p is not None                  display sll    str p info      t                  p   p link              print display sll           except Exception as e              print   Error     e        def insert node in beginning self  data                       Inserts an integer in the beginning of the linked list                      try              temp   Node data              temp link   self start             self start   temp         except Exception as e              print   Error     e       def insert node at end self  data                       Inserts an integer at the end of the linked list                      try                          temp   Node data              if self start is None                  self start   temp                 return              p   self start               while p link is not None                  p   p link             p link   temp         except Exception as e              print   Error     e        def insert node after another self  data  x                       Inserts an integer after the x node                      try              p   self start              while p is not None                  if p info    x                      break                 p   p link              if p is None                  print f  Sorry   x  is not in the list                else                  temp   Node data                  temp link   p link                 p link   temp         except Exception as e               print   Error     e        def insert node before another self  data  x                       Inserts an integer before the x node                       try                 If list is empty             if self start is None                  print   Sorry  The list is empty                    return                If x is the first node  and new node should be inserted before the first node             if x    self start info                  temp   Node data                  temp link   p link                 p link   temp                Finding the reference to the prior node containing x             p   self start             while p link is not None                  if p link info    x                      break                 p   p link              if p link is not None                  print f  Sorry   x  is not in the list                else                  temp   Node data                  temp link   p link                 p link   temp                     except Exception as e              print   Error     e       def insert node at position self  data  k                       Inserts an integer in k position of the linked list                      try                if we wish to insert at the first node             if k    1                  temp   Node data                  temp link   self start                 self start   temp                 return              p   self start             i   1              while i  lt  k-1 and p is not None                  p   p link                 i    1              if p is None                  print f  The max position is  i                 else                      temp   Node data                  temp link   self start                 self start   temp          except Exception as e              print   Error     e       def delete a node self  x                       Deletes a node of a linked list                      try                If list is empty             if self start is None                  print   Sorry  The list is empty                    return                If there is only one node             if self start info    x                  self start   self start link                If more than one node exists             p   self start             while p link is not None                  if p link info    x                      break                    p   p link              if p link is None                  print f  Sorry   x  is not in the list                else                  p link   p link link          except Exception as e              print   Error     e       def delete sll first node self                       Deletes the first node of a linked list                      try              if self start is None                  return             self start   self start link          except Exception as e              print   Error     e        def delete sll last node self                       Deletes the last node of a linked list                      try                 If the list is empty             if self start is None                  return                If there is only one node             if self start link is None                  self start   None                 return                If there is more than one node                 p   self start                Increment until we find the node prior to the last node              while p link link is not None                  p   p link              p link   None             except Exception as e              print   Error     e        def reverse sll self                       Reverses the linked list                       try               prev   None             p   self start             while p is not None                  next   p link                 p link   prev                 prev   p                 p   next             self start   prev          except Exception as e              print   Error     e        def bubble sort sll nodes data self                       Bubble sorts the linked list on integer values                       try                 If the list is empty or there is only one node             if self start is None or self start link is None                  print   The list has no or only one node and sorting is not required                end   None              while end    self start link                  p   self start                 while p link    end                      q   p link                     if p info  gt  q info                          p info  q info   q info  p info                     p   p link                 end   p          except Exception as e              print   Error     e        def bubble sort sll self                       Bubble sorts the linked list                       try                 If the list is empty or there is only one node             if self start is None or self start link is None                  print   The list has no or only one node and sorting is not required                end   None              while end    self start link                  r   p   self start                 while p link    end                      q   p link                     if p info  gt  q info                          p link   q link                         q link   p                     if  p    self start                          r link   q link                     else                          self start   q                     p  q   q  p                     r   p                     p   p link                 end   p          except Exception as e              print   Error     e        def sll has cycle self                       Tests the list for cycles using Tortoise and Hare Algorithm  Floyd s cycle detection algorithm                       try               if self find sll cycle   is None                  return False             else                  return True           except Exception as e              print   Error     e        def find sll cycle self                       Finds cycles in the list  if any                      try                 If there is one node or none  there is no cycle             if self start is None or self start link is None                  return None                Otherwise               slowR   self start             fastR   self start              while slowR is not None and fastR is not None                  slowR   slowR link                 fastR   fastR link link                 if slowR    fastR                       return slowR              return None          except Exception as e              print   Error     e        def remove cycle from sll self                       Removes the cycles                      try               c   self find sll cycle                  If there is no cycle             if c is None                  return              print f  There is a cycle at node     c info               p   c             q   c             len cycles   0             while True                  len cycles    1                 q   q link                  if p    q                      break              print f  The cycle length is  len cycles                 len rem list   0             p   self start              while p    q                  len rem list    1                 p   p link                 q   q link              print f  The number of nodes not included in the cycle is  len rem list                 length list   len rem list   len cycles              print f  The SLL length is  length list                   This for loop goes to the end of the SLL  and set the last node to None and the cycle is removed               p   self start             for   in range length list-1                   p   p link             p link   None           except Exception as e              print   Error     e        def insert cycle in sll self  x                       Inserts a cycle at a node that contains x                       try               if self start is None                  return False              p   self start             px   None             prev   None               while p is not None                  if p info    x                      px   p                 prev   p                 p   p link              if px is not None                  prev link   px             else                  print f  Sorry   x  is not in the list              except Exception as e              print   Error     e        def merge using new list self  list2                       Merges two already sorted SLLs by creating new lists                     merge list   SingleLinkedList           merge list start   self  merge using new list self start  list2 start          return merge list      def  merge using new list self  p1  p2                       Private method of merge using new list                     if p1 info  lt   p2 info              Start merge   Node p1 info              p1   p1 link         else              Start merge   Node p2 info              p2   p2 link                     pM   Start merge          while p1 is not None and p2 is not None              if p1 info  lt   p2 info                  pM link   Node p1 info                  p1   p1 link             else                  pM link   Node p2 info                  p2   p2 link             pM   pM link           If the second list is finished  yet the first list has some nodes         while p1 is not None              pM link   Node p1 info              p1   p1 link             pM   pM link           If the second list is finished  yet the first list has some nodes         while p2 is not None              pM link   Node p2 info              p2   p2 link             pM   pM link          return Start merge      def merge inplace self  list2                       Merges two already sorted SLLs in place in O 1  of space                     merge list   SingleLinkedList           merge list start   self  merge inplace self start  list2 start          return merge list      def  merge inplace self  p1  p2                       Merges two already sorted SLLs in place in O 1  of space                     if p1 info  lt   p2 info              Start merge   p1             p1   p1 link         else              Start merge   p2             p2   p2 link         pM   Start merge          while p1 is not None and p2 is not None              if p1 info  lt   p2 info                  pM link   p1                 pM   pM link                 p1   p1 link             else                  pM link   p2                 pM   pM link                 p2   p2 link          if p1 is None              pM link   p2         else              pM link   p1          return Start merge      def merge sort sll self                       Sorts the linked list using merge sort algorithm                     self start   self  merge sort recursive self start        def  merge sort recursive self  list start                       Recursively calls the merge sort algorithm for two divided lists                        If the list is empty or has only one node         if list start is None or list start link is None              return list start            If the list has two nodes or more         start one   list start         start two   self  divide list self start          start one   self  merge sort recursive start one          start two   self  merge sort recursive start two          start merge   self  merge inplace start one  start two           return start merge      def  divide list self  p                       Divides the linked list into two almost equally sized lists                        Refers to the third nodes of the list         q   p link link          while q is not None and p is not None                Increments p one node at the time             p   p link               Increments q two nodes at the time             q   q link link          start two   p link         p link   None          return start two      def concat second list to sll self  list2                       Concatenates another SLL to an existing SLL                        If the second SLL has no node         if list2 start is None              return            If the original SLL has no node         if self start is None              self start   list2 start             return            Otherwise traverse the original SLL         p   self start         while p link is not None              p   p link            Link the last node to the first node of the second SLL         p link   list2 start        def test merge using new list and inplace self                                     LIST ONE   SingleLinkedList           LIST TWO   SingleLinkedList            LIST ONE create single linked list           LIST TWO create single linked list            print  1    The unsorted first list is             LIST ONE display sll            print  2    The unsorted second list is             LIST TWO display sll             LIST ONE bubble sort sll nodes data           LIST TWO bubble sort sll nodes data            print  1    The sorted first list is             LIST ONE display sll            print  2    The sorted second list is             LIST TWO display sll            LIST THREE   LIST ONE merge using new list LIST TWO           print  The merged list by creating a new list is             LIST THREE display sll             LIST FOUR   LIST ONE merge inplace LIST TWO           print  The in-place merged list is             LIST FOUR display sll              def test all methods self                       Tests all methods of the SLL class                      OPTIONS HELP            Select a method from 1-19                                                                           1       Create a single liked list  SLL                 2       Display the SLL                                            3       Count the nodes of SLL                 4       Search the SLL                5       Insert a node at the beginning of the SLL                6       Insert a node at the end of the SLL                7       Insert a node after a specified node of the SLL                8       Insert a node before a specified node of the SLL                9       Delete the first node of SLL                10      Delete the last node of the SLL                11      Delete a node you wish to remove                                           12      Reverse the SLL                13      Bubble sort the SLL by only exchanging the integer values                  14      Bubble sort the SLL by exchanging links                                    15      Merge sort the SLL                16      Insert a cycle in the SLL                17      Detect if the SLL has a cycle                18      Remove cycle in the SLL                19      Test merging two bubble-sorted SLLs                20      Concatenate a second list to the SLL                 21      Exit                         self create single linked list            while True               print OPTIONS HELP               UI OPTION   int input     Enter an integer for the method you wish to run using the above help                   if UI OPTION    1                  data   int input     Enter an integer to be inserted at the end of the list                      x   int input     Enter an integer to be inserted after that                      self insert node after another data  x              elif UI OPTION    2                  self display sll               elif UI OPTION    3                  self count sll nodes               elif UI OPTION    4                  data   int input     Enter an integer to be searched                      self search sll nodes data              elif UI OPTION    5                  data   int input     Enter an integer to be inserted at the beginning                      self insert node in beginning data              elif UI OPTION    6                  data   int input     Enter an integer to be inserted at the end                      self insert node at end data              elif UI OPTION    7                  data   int input     Enter an integer to be inserted                      x   int input     Enter an integer to be inserted before that                      self insert node before another data  x              elif UI OPTION    8                  data   int input     Enter an integer for the node to be inserted                      k   int input     Enter an integer for the position at which you wish to insert the node                      self insert node before another data  k              elif UI OPTION    9                  self delete sll first node               elif UI OPTION    10                  self delete sll last node               elif UI OPTION    11                  data   int input     Enter an integer for the node you wish to remove                      self delete a node data              elif UI OPTION    12                  self reverse sll               elif UI OPTION    13                  self bubble sort sll nodes data               elif UI OPTION    14                  self bubble sort sll               elif UI OPTION    15                  self merge sort sll               elif UI OPTION    16                  data   int input     Enter an integer at which a cycle has to be formed                      self insert cycle in sll data              elif UI OPTION    17                  if self sll has cycle                        print   The linked list has a cycle                     else                      print   YAAAY  The linked list does not have a cycle                 elif UI OPTION    18                  self remove cycle from sll               elif UI OPTION    19                  self test merge using new list and inplace               elif UI OPTION    20                  list2   self create single linked list                   self concat second list to sll list2              elif UI OPTION    21                  break             else                  print   Option must be an integer  between 1 to 21                 print           if   name         main           Instantiates a new SLL object     SLL OBJECT   SingleLinkedList       SLL OBJECT test all methods

User · Answer

The accepted answer is rather complicated  Here is a more standard design   L   LinkedList   L insert 1  L insert 1  L insert 2  L insert 4  print L L clear   print L   It is a simple LinkedList class based on the straightforward C   design and Chapter 17  Linked lists  as recommended by Thomas Watnedal   class Node      def   init   self  value   None  next   None           self value   value         self next   next      def   str   self           return  Node    str self value       class LinkedList      def   init   self           self first   None         self last   None      def insert self  x           if self first    None              self first   Node x  None              self last   self first         elif self last    self first              self last   Node x  None              self first next   self last         else              current   Node x  None              self last next   current             self last   current      def   str   self           if self first    None              current   self first             out    LinkedList   n   str current value     n              while current next    None                  current   current next                 out    str current value      n              return out               return  LinkedList          def clear self           self   init

User · Answer

Sample of a doubly linked list  save as linkedlist py     class node      def   init   self  before None  cargo None  next None            self  previous   before         self  cargo   cargo          self  next    next       def   str   self           return str self  cargo  or None   class linkedList      def   init   self            self  head   None          self  length   0      def add self  cargo           n   node None  cargo  self  head          if self  head              self  head  previous   n         self  head   n         self  length    1      def search self cargo           node   self  head         while  node and node  cargo    cargo               node   node  next         return node      def delete self cargo           node   self search cargo          if node              prev   node  previous             nx   node  next             if prev                  prev  next   node  next             else                  self  head   nx                 nx  previous   None             if nx                  nx  previous   prev              else                  prev  next   None         self  length -  1      def   str   self           print  Size of linked list    self  length         node   self  head         while node              print node             node   node  next   Testing  save as test py    from linkedlist import node  linkedList  def test         print  Testing Linked List       l   linkedList        l add 10      l add 20      l add 30      l add 40      l add 50      l add 60       print  Linked List after insert nodes       l   str          print  Search some value  30       node   l search 30      print node      print  Delete some value  30       node   l delete 30      l   str          print  Delete first element  60       node   l delete 60      l   str          print  Delete last element  10       node   l delete 10      l   str       if   name         main         test     Output   Testing Linked List Linked List after insert nodes  Size of linked list   6 60 50 40 30 20 10 Search some value  30  30 Delete some value  30  Size of linked list   5 60 50 40 20 10 Delete first element  60  Size of linked list   4 50 40 20 10 Delete last element  10  Size of linked list   3 50 40 20

User · Answer

Here is my simple implementation    class Node      def   init   self           self data   None         self next   None     def   str   self           return  Data  s  Next - gt   s   self data  self next   class LinkedList      def   init   self           self head   Node           self curNode   self head     def insertNode self  data           node   Node           node data   data         node next   None         if self head data    None              self head   node             self curNode   node         else              self curNode next   node             self curNode   node     def printList self           print self head  l   LinkedList   l insertNode 1  l insertNode 2  l insertNode 34    Output   Data 1  Next - gt  Data 2  Next - gt  Data 34  Next - gt  Data 4  Next - gt  None

User · Answer

The following is what I came up with  It s similer to Riccardo C  s  in this thread  except it prints the numbers in order instead of in reverse  I also made the LinkedList object a Python Iterator in order to print the list out like you would a normal Python list   class Node       def   init   self  data None           self data   data         self next   None      def   str   self           return str self data    class LinkedList       def   init   self           self head   None         self curr   None         self tail   None      def   iter   self           return self      def next self           if self head and not self curr              self curr   self head             return self curr         elif self curr next              self curr   self curr next             return self curr         else              raise StopIteration      def append self  data           n   Node data          if not self head              self head   n             self tail   n         else              self tail next   n             self tail   self tail next     Add 5 nodes ll   LinkedList   for i in range 1  6       ll append i     print out the list for n in ll      print n      Example output    python linked list py 1 2 3 4 5

User · Answer

If you want to just create a simple liked list then refer this code  l  1  2  3  4  5  6  7  8  9  10            for visualize execution for this cod Visit http   www pythontutor com visualize html mode edit

User · Answer

class Node object       def   init   self  data None  next None           self data   data         self next   next      def setData self  data           self data   data         return self data      def setNext self  next           self next   next      def getNext self           return self next      def hasNext self           return self next    None   class singleLinkList object        def   init   self           self head   None      def isEmpty self           return self head    None      def insertAtBeginning self  data           newNode   Node           newNode setData data           if self listLength      0              self head   newNode         else              newNode setNext self head              self head   newNode      def insertAtEnd self  data           newNode   Node           newNode setData data           current   self head          while current getNext      None              current   current getNext            current setNext newNode       def listLength self           current   self head         count   0          while current    None              count    1             current   current getNext           return count      def print llist self           current   self head         print  List Start            while current    None              print current getData                current   current getNext            print  List End       if   name         main         ll   singleLinkList       ll insertAtBeginning 55      ll insertAtEnd 56      ll print llist       print ll listLength

User · Answer

Here is my simple implementation    class Node      def   init   self           self data   None         self next   None     def   str   self           return  Data  s  Next - gt   s   self data  self next   class LinkedList      def   init   self           self head   Node           self curNode   self head     def insertNode self  data           node   Node           node data   data         node next   None         if self head data    None              self head   node             self curNode   node         else              self curNode next   node             self curNode   node     def printList self           print self head  l   LinkedList   l insertNode 1  l insertNode 2  l insertNode 34    Output   Data 1  Next - gt  Data 2  Next - gt  Data 34  Next - gt  Data 4  Next - gt  None

User · Answer

Here is some list functions based on Martin v  L  wis s representation   cons     lambda el  lst   el  lst  mklist   lambda  args  reduce lambda lst  el  cons el  lst   reversed args   None  car   lambda lst  lst 0  if lst else lst cdr   lambda lst  lst 1  if lst else lst nth   lambda n  lst  nth n-1  cdr lst   if n  gt  0 else car lst  length    lambda lst  count 0  length cdr lst   count 1  if lst else count begin     lambda  args  args -1  display   lambda lst  begin w   s     car lst    display cdr lst    if lst else w  nil n     where w   sys stdout write  Although doubly linked lists are famously used in Raymond Hettinger s ordered set recipe  singly linked lists have no practical value in Python   I ve never used a singly linked list in Python for any problem except educational    Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist  Chapter 17  Linked lists   A linked list is either     the empty list  represented by None  or  a node that contains a cargo object and a reference to a linked list   class Node     def   init   self  cargo None  next None        self car   cargo      self cdr   next       def   str   self        return str self car   def display lst     if lst      w   s     lst      display lst cdr    else      w  nil n

User · Answer

My 2 cents   class Node      def   init   self  value None  next None           self value   value         self next   next      def   str   self           return str self value    class LinkedList      def   init   self           self first   None         self last   None      def add self  x           current   Node x  None          try              self last next   current         except AttributeError              self first   current             self last   current         else              self last   current      def print list self           node   self first         while node              print node value             node   node next  ll   LinkedList   ll add  1st   ll add  2nd   ll add  3rd   ll add  4th   ll add  5th    ll print list      Result     1st   2nd   3rd   4th   5th

User · Answer

For some needs  a deque may also be useful  You can add and remove items on both ends of a deque at O 1  cost   from collections import deque d   deque  1 2 3 4    print d for x in d      print x print d pop    d

User · Answer

Here is my solution   Implementation  class Node    def   init   self  initdata       self data   initdata     self next   None    def get data self       return self data    def set data self  data       self data   data    def get next self       return self next    def set next self  node       self next   node     ------------------------ Link List class -------------------------------   class LinkList     def   init   self       self head   None    def is empty self       return self head    None    def traversal self  data None       node   self head     index   0     found   False     while node is not None and not found        if node get data      data          found   True       else          node   node get next           index    1     return  node  index     def size self          count   self traversal None      return count    def search self  data       node      self traversal data      return node    def add self  data       node   Node data      node set next self head      self head   node    def remove self  data       previous node   None     current node   self head     found   False     while current node is not None and not found        if current node get data      data          found   True         if previous node            previous node set next current node get next            else            self head   current node       else          previous node   current node         current node   current node get next       return found   Usage  link list   LinkList   link list add 10  link list add 20  link list add 30  link list add 40  link list add 50  link list size   link list search 30  link list remove 20    Original Implementation Idea     http   interactivepython org runestone static pythonds BasicDS ImplementinganUnorderedListLinkedLists html

User · Answer

I think the implementation below fill the bill quite gracefully      singly linked lists  by Yingjie Lan  December 1st  2011     class linkst         Singly linked list  with pythonic features  The list has pointers to both the first and the last node           slots       data    next    memory efficient     def   init   self  iterable     data None  next None              Provide an iterable to make a singly linked list  Set iterable to None to make a data node for internal use             if iterable is not None               self data  self next   self  None             self extend iterable          else   a common node             self data  self next   data  next      def empty self              test if the list is empty            return self next is None      def append self  data              append to the end of list             last   self data         self data   last next   linkst None  data           self data   last next      def insert self  data  index 0              insert data before index  Raise IndexError if index is out of range            curr  cat   self  0         while cat  lt  index and curr              curr  cat   curr next  cat 1         if index lt 0 or not curr              raise IndexError index          new   linkst None  data  curr next          if curr next is None  self data   new         curr next   new      def reverse self              reverse the order of list in place            current  prev   self next  None         while current   what if list is empty              next   current next             current next   prev             prev  current   current  next         if self next  self data   self next         self next   prev      def delete self  index 0              remvoe the item at index from the list            curr  cat   self  0         while cat  lt  index and curr next              curr  cat   curr next  cat 1         if index lt 0 or not curr next              raise IndexError index          curr next   curr next next         if curr next is None   tail             self data   curr  current    self       def remove self  data              remove first occurrence of data  Raises ValueError if the data is not present             current   self         while current next   node to be examined             if data    current next data  break             current   current next  move on         else  raise ValueError data          current next   current next next         if current next is None   tail             self data   current  current    self       def   contains   self  data              membership test using keyword  in              current   self next         while current              if data    current data                  return True             current   current next         return False      def   iter   self              iterate through list by for-statements  return an iterator that must define the   next   method             itr   linkst           itr next   self next         return itr  invariance  itr data    itr      def   next   self              the for-statement depends on this method to provide items one by one in the list  return the next data  and move on              the invariance is checked so that a linked list          will not be mistakenly iterated over         if self data is not self or self next is None              raise StopIteration           next   self next         self next   next next         return next data      def   repr   self              string representation of the list            return  linkst  r   list self       def   str   self              converting the list to a string            return  - gt   join str i  for i in self        note  this is NOT the class lab  see file linked py      def extend self  iterable              takes an iterable  and append all items in the iterable to the end of the list self             last   self data         for i in iterable              last next   linkst None  i              last   last next         self data   last      def index self  data              TODO  return first index of data in the list self      Raises ValueError if the value is not present              must not convert self to a tuple or any other containers         current  idx   self next  0         while current              if current data    data  return idx             current  idx   current next  idx 1         raise ValueError data

User · Answer

Here is some list functions based on Martin v  L  wis s representation   cons     lambda el  lst   el  lst  mklist   lambda  args  reduce lambda lst  el  cons el  lst   reversed args   None  car   lambda lst  lst 0  if lst else lst cdr   lambda lst  lst 1  if lst else lst nth   lambda n  lst  nth n-1  cdr lst   if n  gt  0 else car lst  length    lambda lst  count 0  length cdr lst   count 1  if lst else count begin     lambda  args  args -1  display   lambda lst  begin w   s     car lst    display cdr lst    if lst else w  nil n     where w   sys stdout write  Although doubly linked lists are famously used in Raymond Hettinger s ordered set recipe  singly linked lists have no practical value in Python   I ve never used a singly linked list in Python for any problem except educational    Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist  Chapter 17  Linked lists   A linked list is either     the empty list  represented by None  or  a node that contains a cargo object and a reference to a linked list   class Node     def   init   self  cargo None  next None        self car   cargo      self cdr   next       def   str   self        return str self car   def display lst     if lst      w   s     lst      display lst cdr    else      w  nil n

User · Answer

enter code here enter code here  class node      def   init   self           self data   None         self next   None class linked list      def   init   self           self cur node   None         self head   None     def add node self data           new node   node           if self head    None              self head   new node             self cur node   new node         new node data   data         new node next   None         self cur node next   new node         self cur node   new node     def list print self           node   self head         while node              print  node data              node   node next     def delete self           node   self head         next node   node next         del node          self head   next node a   linked list   a add node 1  a add node 2  a add node 3  a add node 4  a delete   a list print

User · Answer

Linked List Class  class LinkedStack    Nested Node Class class Node      def   init   self  element  next           self   element   element         self   next   next      def get next self           return self   next      def get element self           return self   element  def   init   self       self head   None     self size   0     self data       def   len   self       return self size  def   str   self       return str self data   def is empty self       return self size    0  def push self  e       newest   self Node e  self head      self head   newest     self size    1     self data append newest   def top self       if self is empty            raise Empty  Stack is empty       return self head   element  def pop self       if self is empty            raise Empty  Stack is empty       answer   self head element     self head   self head next     self size -  1     return answer   Usage  from LinkedStack import LinkedStack  x   LinkedStack    x push 10  x push 25  x push 55    for i in range x size - 1  -1  -1        print      x data i  get element               next object      if x data i  get next      None          print  -- gt  None      else          print  x data i  get next   get element     - ---- gt        Output     55   25 - ---- gt      25   10 - ---- gt      10   -- gt  None

User · Answer

I wrote this up the other day      usr bin env python  class Node object       def   init   self           self data   None   contains the data         self next   None   contains the reference to the next node   class LinkedList      def   init   self           self cur node   None      def add node self  data           new node   Node     create a new node         new node data   data         new node next   self cur node   link the new node to the  previous  node          self cur node   new node    set the current node to the new one       def list print self           node   self cur node   cant point to ll          while node              print node data             node   node next    ll   LinkedList   ll add node 1  ll add node 2  ll add node 3   ll list print

User · Answer

Expanding Nick Stinemates s answer  class Node object       def   init   self           self data   None         self next   None  class LinkedList      def   init   self           self head   None      def prepend node self  data           new node   Node           new node data   data         new node next   self head         self head   new node      def append node self  data           new node   Node           new node data   data         current   self head         while current next              current   current next         current next   new node      def reverse self               In-place reversal  modifies exiting list            previous   None         current node   self head          while current node              temp    current node next             current node next   previous             previous   current node             current node   temp         self head   previous      def search self  data           current node   self head         try              while current node data    data                  current node   current node next             return True         except              return False      def display self           if self head is None              print  Linked list is empty           else              current node   self head             while current node                  print current node data                  current node   current node next      def list length self           list length   0         current node   self head         while current node              list length    1             current node   current node next         return list length   def main        linked list   LinkedList        linked list prepend node 1      linked list prepend node 2      linked list prepend node 3      linked list append node 24      linked list append node 25      linked list display       linked list reverse       linked list display       print linked list search 1       linked list reverse       linked list display       print  Lenght of singly linked list is      str linked list list length       if   name         main         main

User · Answer

The following is what I came up with  It s similer to Riccardo C  s  in this thread  except it prints the numbers in order instead of in reverse  I also made the LinkedList object a Python Iterator in order to print the list out like you would a normal Python list   class Node       def   init   self  data None           self data   data         self next   None      def   str   self           return str self data    class LinkedList       def   init   self           self head   None         self curr   None         self tail   None      def   iter   self           return self      def next self           if self head and not self curr              self curr   self head             return self curr         elif self curr next              self curr   self curr next             return self curr         else              raise StopIteration      def append self  data           n   Node data          if not self head              self head   n             self tail   n         else              self tail next   n             self tail   self tail next     Add 5 nodes ll   LinkedList   for i in range 1  6       ll append i     print out the list for n in ll      print n      Example output    python linked list py 1 2 3 4 5

User · Answer

Here is my solution   Implementation  class Node    def   init   self  initdata       self data   initdata     self next   None    def get data self       return self data    def set data self  data       self data   data    def get next self       return self next    def set next self  node       self next   node     ------------------------ Link List class -------------------------------   class LinkList     def   init   self       self head   None    def is empty self       return self head    None    def traversal self  data None       node   self head     index   0     found   False     while node is not None and not found        if node get data      data          found   True       else          node   node get next           index    1     return  node  index     def size self          count   self traversal None      return count    def search self  data       node      self traversal data      return node    def add self  data       node   Node data      node set next self head      self head   node    def remove self  data       previous node   None     current node   self head     found   False     while current node is not None and not found        if current node get data      data          found   True         if previous node            previous node set next current node get next            else            self head   current node       else          previous node   current node         current node   current node get next       return found   Usage  link list   LinkList   link list add 10  link list add 20  link list add 30  link list add 40  link list add 50  link list size   link list search 30  link list remove 20    Original Implementation Idea     http   interactivepython org runestone static pythonds BasicDS ImplementinganUnorderedListLinkedLists html

User · Answer

I wrote this up the other day      usr bin env python  class Node object       def   init   self           self data   None   contains the data         self next   None   contains the reference to the next node   class LinkedList      def   init   self           self cur node   None      def add node self  data           new node   Node     create a new node         new node data   data         new node next   self cur node   link the new node to the  previous  node          self cur node   new node    set the current node to the new one       def list print self           node   self cur node   cant point to ll          while node              print node data             node   node next    ll   LinkedList   ll add node 1  ll add node 2  ll add node 3   ll list print

User · Answer

When using immutable linked lists  consider using Python s tuple directly    ls    1  2  3  4  5   def first ls   return ls 0  def rest ls   return ls 1     Its really that ease  and you get to keep the additional funcitons like len ls   x in ls  etc

User · Answer

If you want to just create a simple liked list then refer this code  l  1  2  3  4  5  6  7  8  9  10            for visualize execution for this cod Visit http   www pythontutor com visualize html mode edit

User · Answer

class LL object       def   init   self val           self val   val         self next   None      def pushNodeEnd self top val           if top is None              top val val             top next None         else              tmp top             while  tmp next    None                   tmp tmp next                     newNode LL val              newNode next None             tmp next newNode      def pushNodeFront self top val           if top is None              top val val             top next None         else              newNode LL val              newNode next top             top newNode      def popNodeFront self top           if top is None              return         else              sav top             top top next         return sav      def popNodeEnd self top           if top is None              return         else              tmp top             while  tmp next    None                   prev tmp                 tmp tmp next             prev next None         return tmp  top LL 10  top pushNodeEnd top  20  top pushNodeEnd top  30  pop top popNodeEnd top  print  pop val

User · Answer

When using immutable linked lists  consider using Python s tuple directly    ls    1  2  3  4  5   def first ls   return ls 0  def rest ls   return ls 1     Its really that ease  and you get to keep the additional funcitons like len ls   x in ls  etc

User · Answer

I just did this as a fun toy  It should be immutable as long as you don t touch the underscore-prefixed methods  and it implements a bunch of Python magic like indexing and len

User · Answer

When using immutable linked lists  consider using Python s tuple directly    ls    1  2  3  4  5   def first ls   return ls 0  def rest ls   return ls 1     Its really that ease  and you get to keep the additional funcitons like len ls   x in ls  etc

User · Answer

Immutable lists are best represented through two-tuples  with None representing NIL  To allow simple formulation of such lists  you can use this function   def mklist  args       result   None     for element in reversed args           result    element  result      return result   To work with such lists  I d rather provide the whole collection of LISP functions  i e  first  second  nth  etc   than introducing methods

User · Answer

I just did this as a fun toy  It should be immutable as long as you don t touch the underscore-prefixed methods  and it implements a bunch of Python magic like indexing and len

User · Answer

Here s a slightly more complex version of a linked list class  with a similar interface to python s sequence types  ie  supports indexing  slicing  concatenation with arbitrary sequences etc    It should have O 1  prepend  doesn t copy data unless it needs to and can be used pretty interchangably with tuples   It won t be as space or time efficient as lisp cons cells  as python classes are obviously a bit more heavyweight  You could improve things slightly with    slots       head    tail   to reduce memory usage    It will have the desired big O performance characteristics however   Example of usage    gt  gt  gt  l   LinkedList  1 2 3 4    gt  gt  gt  l LinkedList  1  2  3  4    gt  gt  gt  l head  l tail  1  LinkedList  2  3  4       Prepending is O 1  and can be done with  LinkedList cons 0  l  LinkedList  0  1  2  3  4     Or prepending arbitrary sequences  Still no copy of l performed    -1 0    l LinkedList  -1  0  1  2  3  4      Normal list indexing and slice operations can be performed    Again  no copy is made unless needed   gt  gt  gt  l 1   l -1   l 2    2  4  LinkedList  3  4     gt  gt  gt  assert l 2   is l next next    For cases where the slice stops before the end  or uses a   non-contiguous range  we do need to create a copy   However   this should be transparent to the user   gt  gt  gt  LinkedList range 100   -10  2  LinkedList  90  92  94  96  98     Implementation   import itertools  class LinkedList object          Immutable linked list class          def   new   cls  l              if isinstance l  LinkedList   return l   Immutable  so no copy needed          i   iter l          try              head   i next           except StopIteration              return cls EmptyList     Return empty list singleton           tail   LinkedList i           obj   super LinkedList  cls    new   cls          obj  head   head         obj  tail   tail         return obj       classmethod     def cons cls  head  tail           ll    cls  head           if not isinstance tail  cls               tail   cls tail          ll  tail   tail         return ll        head and tail are not modifiable      property       def head self   return self  head       property     def tail self   return self  tail      def   nonzero   self   return True      def   len   self           return sum 1 for   in self       def   add   self  other           other   LinkedList other           if not self  return other          l   l         start l   LinkedList iter self      Create copy  as we ll mutate          while l              if not l  tail    Last element                  l  tail   other                 break             l   l  tail         return start      def   radd   self  other           return LinkedList other    self      def   iter   self           x self         while x              yield x head             x x tail      def   getitem   self  idx              Get item at specified index            if isinstance idx  slice                 Special case  Avoid constructing a new list  or performing O n  length                calculation for slices like l 3     Since we re immutable  just return               the appropriate node  This becomes O start  rather than O n                 We can t do this for  more complicated slices however  eg  l 4              start   idx start or 0             if  start  gt   0  and  idx stop is None  and  idx step is None or idx step    1                   no copy needed True             else                  length   len self     Need to calc length                  start  stop  step   idx indices length                  no copy needed    stop    length  and  step    1               if no copy needed                  l   self                 for i in range start                        if not l  break   End of list                      l l tail                 return l             else                    We need to construct a new list                  if step  lt  1     Need to instantiate list to deal with -ve step                     return LinkedList list self  start stop step                   else                      return LinkedList itertools islice iter self   start  stop  step           else                       Non-slice index              if idx  lt  0  idx   len self  idx             if not self  raise IndexError  list index out of range               if idx    0  return self head             return self tail idx-1       def   mul   self  n           if n  lt   0  return Nil         l self         for i in range n-1   l    self         return l     def   rmul   self  n   return self   n        Ideally we should compute the has ourselves rather than construct       a temporary tuple as below   I haven t impemented this here     def   hash   self   return hash tuple self        def   eq   self  other   return self  cmp other     0     def   ne   self  other   return not self    other     def   lt   self  other   return self  cmp other   lt  0     def   gt   self  other   return self  cmp other   gt  0     def   le   self  other   return self  cmp other   lt   0     def   ge   self  other   return self  cmp other   gt   0      def  cmp self  other              Acts as cmp    -1 for self lt other  0 for equal  1 for greater            if not isinstance other  LinkedList               return cmp LinkedList type other      Arbitrary ordering           A  B   iter self   iter other          for a b in itertools izip A B              if a lt b  return -1            elif a  gt  b  return 1          try              A next               return 1    a has more items          except StopIteration  pass          try              B next               return -1    b has more items          except StopIteration  pass          return 0    Lists are equal      def   repr   self           return  LinkedList   s           join map repr self    class EmptyList LinkedList          A singleton representing an empty list         def   new   cls           return object   new   cls       def   iter   self   return iter         def   nonzero   self   return False       property     def head self   raise IndexError  End of list         property     def tail self   raise IndexError  End of list      Create EmptyList singleton LinkedList EmptyList   EmptyList   del EmptyList

[python] Python Linked List

Examples related to python

Examples related to linked-list