Связанный список Python

Какой самый простой способ использовать связанный список в python? В схеме связанный список определяется просто '(1 2 3 4 5) . Списки Python, [1, 2, 3, 4, 5] и кортежи (1, 2, 3, 4, 5) не являются, по сути, связанными списками, а связанные списки имеют некоторые приятные свойства, и может ссылаться на отдельные части. Сделайте их неизменными, и с ними действительно легко работать!

  • Удаление номеров из строки
  • регулярное выражение для анализа конфигурации сетевого интерфейса
  • Сокеты Python - сохранить розетку в розетке?
  • выполнение заданий на пользовательских классах в python
  • PyQT4 WheelEvent? как определить, использовалось ли колесо?
  • Анализ аудио с использованием быстрого преобразования Фурье
  • Ошибка при вызове баз метакласса: аргумент функции () должен быть кодом, а не str
  • Различное поведение для списка .__ iadd__ и list .__ add__
  • 28 Solutions collect form web for “Связанный список Python”

    Вот некоторые функции списка, основанные на представлении Мартина против Лёвиса :

     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 > 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") 

    где w = sys.stdout.write

    Несмотря на то, что списки с двойным связыванием классически используются в рецептном рецепте Раймона Хеттингера, отдельные списки не имеют практического значения в Python.

    Я никогда не использовал одиночный список в Python для любой проблемы, кроме образовательной.

    Томас Уотнедал предложил хороший образовательный ресурс « Как думать, как компьютерный ученый», глава 17: Связанные списки :

    Связанный список:

    • пустой список, представленный None, или
    • узел, который содержит грузовой объект и ссылку на связанный список.

       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") 

    Для некоторых потребностей также может быть полезен deque . Вы можете добавлять и удалять элементы на обоих концах deque по цене O (1).

     from collections import deque d = deque([1,2,3,4]) print d for x in d: print x print d.pop(), d 

    Я написал это на днях

     #! /usr/bin/env python class node: def __init__(self): self.data = None # contains the data self.next = None # contains the reference to the next node class linked_list: 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 = linked_list() ll.add_node(1) ll.add_node(2) ll.add_node(3) ll.list_print() 

    Принятый ответ довольно сложен. Вот более стандартный дизайн:

     L = LinkedList() L.insert(1) L.insert(1) L.insert(2) L.insert(4) print L L.clear() print L 

    Это простой класс LinkedList на основе простой конструкции C ++ и главы 17: Связанные списки , как рекомендовал Томас Уотдаль .

     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__() 

    Неизменяемые списки лучше всего представлены через два кортежа, а None – NIL. Чтобы упростить составление таких списков, вы можете использовать эту функцию:

     def mklist(*args): result = None for element in reversed(args): result = (element, result) return result 

    Чтобы работать с такими списками, я предпочел бы предоставить всю коллекцию функций LISP (т.е., первая, вторая, n-я и т. Д.), А не вводить методы.

    Вот несколько более сложная версия связанного класса списка, с похожим интерфейсом к типам последовательностей python (т. Е. Поддерживает индексирование, нарезку, конкатенацию с произвольными последовательностями и т. Д.). Он должен иметь O (1) preend, не копировать данные, если это необходимо, и может быть использовано довольно взаимозаменяемо с кортежами.

    Это не так просто, как пространство или время, как lisp cons cells, поскольку классы python явно немного __slots__ = '_head','_tail' (вы можете немного улучшить ситуацию с помощью « __slots__ = '_head','_tail' »), чтобы уменьшить использование памяти). Однако он будет иметь желаемые характеристики производительности O.

    Пример использования:

     >>> l = LinkedList([1,2,3,4]) >>> l LinkedList([1, 2, 3, 4]) >>> 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. >>> l[1], l[-1], l[2:] (2, 4, LinkedList([3, 4])) >>> 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. >>> LinkedList(range(100))[-10::2] LinkedList([90, 92, 94, 96, 98]) 

    Реализация:

     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 >= 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 < 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 < 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 <= 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) < 0 def __gt__(self, other): return self._cmp(other) > 0 def __le__(self, other): return self._cmp(other) <= 0 def __ge__(self, other): return self._cmp(other) >= 0 def _cmp(self, other): """Acts as cmp(): -1 for self<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<b: return -1 elif a > 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 
     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()) 

    Я основывал эту дополнительную функцию на 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 

    Метод, который он добавляет новый узел в начале, в то время как я видел много реализаций, которые обычно добавляют новый узел в конце, но что угодно, это весело.

    Ниже приводится то, что я придумал. Это симилятор Риккардо С. , в этой теме, за исключением того, что он печатает цифры в порядке, а не наоборот. Я также создал объект LinkedList Python Iterator для печати списка, как и обычный список Python.

     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 """ 

    Я просто сделал это как забавную игрушку. Он должен быть неизменным, если вы не трогаете методы подчеркивания с префиксом, и он реализует кучу магии Python, например индексирование и len .

    При использовании неизменяемых связанных списков, используйте прямое кортеж Python.

     ls = (1, 2, 3, 4, 5) def first(ls): return ls[0] def rest(ls): return ls[1:] 

    Это действительно такая легкость, и вы можете сохранить дополнительные функции, такие как len (ls), x в ls и т. Д.

     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) 

    Я поместил список классов Python 2.x и 3.x по отдельности в https://pypi.python.org/pypi/linked_list_mod/

    Он протестирован с CPython 2.7, CPython 3.4, Pypy 2.3.1, Pypy3 2.3.1 и Jython 2.7b2 и поставляется с красивым автоматизированным набором тестов.

    Он также включает классы LIFO и FIFO.

    Однако они не являются неизменными.

    Код, указанный пользователем201788, предназначенный для изменения Prepend в исходном коде Nick Stinemates для Append, не работает. Поскольку self.cur_node не обновляется, он остается равным None, поэтому цикл while никогда не произойдет. Чтобы заставить его работать, нам просто нужно сделать еще одну вещь, изменить инициализацию класса linked_list.

     class linked_list: def __init__(self): #self.cur_node = None # Nick Stinemate's code self.cur_node = node() # in order to "append" 
     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 (ie 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 

    Класс связанного списка

     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 

    Применение

     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 '--> None' else: print x.data[i].get_next().get_element(), '-|----> ', 

    Вывод

     | 55 | 25 -|----> | 25 | 10 -|----> | 10 | --> None 

    Вот моя простая реализация:

     class Node: def __init__(self): self.data = None self.next = None def __str__(self): return "Data %s: Next -> %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) 

    Вывод:

     Data 1: Next -> Data 2: Next -> Data 34: Next -> Data 4: Next -> None 

    Вот довольно схема для этого:

     class cons: def __init__(self, f, r): self.__f = f self.__r = r def __str__(self): return "(%s, %s)" % (str(self.__f), str(self.__r)) __repr__ = __str__ class empty: def __init__(self): pass __repr__ = lambda self: "empty" __str__ = __repr__ empty = empty() def first(self): return self.__f def rest(self): return self.__r 

    Однако я ищу еще один способ python, и в идеале, который легче работать с синтаксисом, чем это:

     >>> cons(12, cons(4, cons.empty)) (12, (4, empty)) >>> cons(12, cons(4, cons.empty)).first() 12 >>> cons(12, cons(4, cons.empty)).rest() (4, empty) 

    Я думаю, что реализация ниже заполняет законопроект довольно изящно.

     '''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 < index and curr: curr, cat = curr.next, cat+1 if index<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 < index and curr.next: curr, cat = curr.next, cat+1 if index<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 '->'.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) 
     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 -> %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) 

    Прежде всего, я предполагаю, что вам нужны связанные списки. На практике вы можете использовать collections.deque , чья текущая реализация CPython представляет собой двусвязный список блоков (каждый блок содержит массив из 62 грузовых объектов). Он включает функциональность связанного списка. Вы также можете найти расширение C, называемое llist на pypi. Если вам нужен чистый Python и простая в использовании реализация связанного списка ADT, вы можете взглянуть на мою следующую минимальную реализацию.

     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) 

    Мои 2 цента

     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 
     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() 

    Я рассматриваю словарь как связанный список.

    Скажем, у нас есть список кошек -> собака -> крыса -> летучая мышь:

     dict1 = {} dict1["root"] = "cat" dict1["cat"] = "dog" dict1["dog"] = "rat" dict1["rat"] = "bat" dict1["bat"] = None 

    Вставка:

     dict1["peacock"] = dict1["dog"] dict1["dog"] = "peacock" 

    Есть ли какие-либо проблемы с этим подходом с точки зрения сложности времени и пространства?

    llist – Связанные списки типов данных для Python

    Модуль llist реализует структуры связанных списков данных, поддерживает двусвязный список, т. е. dllist и структуру данных с одиночной sllist .

    объекты dllist

    Этот объект представляет собой структуру данных с двойной связью.

    first

    Первый объект dllistnode в списке. None если список пуст.

    last

    Последний объект dllistnode в списке. Нет, если список пуст.

    Объекты dllist также поддерживают следующие методы:

    append(x)

    Добавьте x в правую часть списка и верните вставленный dllistnode .

    appendleft(x)

    Добавьте x в левую часть списка и верните вставленный dllistnode .

    appendright(x)

    Добавьте x в правую часть списка и верните вставленный dllistnode .

    clear()

    Удалите все узлы из списка.

    extend(iterable)

    Добавляйте элементы из iterable в правую часть списка.

    extendleft(iterable)

    Добавляйте элементы из iterable в левую часть списка.

    extendright(iterable)

    Добавляйте элементы из iterable в правую часть списка.

    insert(x[, before])

    Добавьте x в правую часть списка, если before не указано, или dllistnode before x в левую часть dllistnode before . Вернуть вставленный dllistnode .

    nodeat(index)

    Возвращаемый узел (типа dllistnode ) по index .

    pop()

    Удалите и верните значение элемента с правой стороны списка.

    popleft()

    Удалите и верните значение элемента с левой стороны списка.

    popright()

    Удалите и верните значение элемента с правой стороны списка

    remove(node)

    Удалите node из списка и верните элемент, который был сохранен в нем.

    Объекты dllistnode

    class llist.dllistnode([value])

    Верните новый узел с двойным соединением, инициализированный (необязательно) со value .

    Объекты dllistnode предоставляют следующие атрибуты:

    next

    Следующий узел в списке. Этот атрибут доступен только для чтения.

    prev

    Предыдущий узел в списке. Этот атрибут доступен только для чтения.

    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.

    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() 

    Выход :

     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 

    Вот мое решение:

    Реализация

     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 

    Применение

     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

    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

    Python - лучший язык программирования в мире.