Python链接列表
在python中使用链表最简单的方法是什么？ 在scheme中，链接列表由'(1 2 3 4 5)简单定义。 Python的列表[1, 2, 3, 4, 5]和元组(1, 2, 3, 4, 5)实际上不是链表，链表具有一些很好的属性，时间串联，并能够引用它们的不同部分。 让他们不变，他们真的很容易与工作！
以下是一些基于Martin v。Löwis表述的列表函数：
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
尽pipe双链表在Raymond Hettinger的有序集合配方中被广泛使用，但是单链表对Python没有实际价值。
除了教育以外，我从来没有在Python中使用单独的链表来处理任何问题。
托马斯Watnedal build议一个良好的教育资源如何像电脑科学家一样思考，第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也可能是有用的。 您可以在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()
被接受的答案相当复杂。 这是一个更标准的devise：
L = LinkedList() L.insert(1) L.insert(1) L.insert(2) L.insert(4) print L L.clear() print L
这是一个简单的LinkedList类，基于简单的C ++devise和Thomas Watnedal推荐的第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的序列types相似的接口（即支持索引，切片，与任意序列的连接等）。 它应该有O（1）prepend，不需要复制数据，除非需要和元组可以互换使用。
它不会像lisp cons单元那样具有空间或时间效率，因为python类显然有点重量级（可以用__slots__ = '_head','_tail'来减less内存使用量。 它将具有所需的大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的这个附加function
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
他在开始的时候添加了新的节点，而我看到了很多通常会在最后添加一个新节点的实现，但无论如何，这很有趣。
以下是我想出来的。 这是Riccardo C.的similer，在这个线程中，除了按顺序打印数字而不是反向打印。 我也使LinkedList对象成为一个Python迭代器，以便像打印正常的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 """
我只是做了一个有趣的玩具。 只要不触及带下划线的前缀方法，它就应该是不可变的，并且它实现了一堆像索引和len一样的Python魔法。
使用不可变链接列表时，请考虑直接使用Python的元组。
ls = (1, 2, 3, 4, 5) def first(ls): return ls[0] def rest(ls): return ls[1:]
它真的很容易，你可以保留像len（ls），x in ls等附加function。
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)
我已经在https://pypi.python.org/pypi/linked_list_mod/上安装了一个Python 2.x和3.x单链表类。
它使用CPython 2.7，CPython 3.4，Pypy 2.3.1，Pypy3 2.3.1和Jython 2.7b2进行testing，并附带一个很好的自动化testing套件。
它还包括LIFO和FIFO类。
尽pipe如此，它们并不是永恒的。
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
我觉得下面的实现比较优雅。
'''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个货物对象的数组）。 它包含链接列表的function。 您也可以在pypi上search名为llist的C扩展名。 如果你想要一个纯粹的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)
llist – Python的链接列表数据types
llist模块实现的链表数据结构支持双向链表，即dllist和单链接数据结构sllist 。
dllist对象
这个对象表示一个双向链表数据结构。
first
列表中的第一个dllistnode对象。 如果列表为空，则无。
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])
如果未指定before ，则将x添加到列表的右侧，或者before将x插入到dllistnode before的左侧。 返回插入的dllistnode 。
nodeat(index)
返回index处的节点（types为dllistnode ）。
pop()
从列表的右侧移除并返回一个元素的值。
popleft()
从列表的左侧移除并返回一个元素的值。
popright()
从列表的右侧移除并返回一个元素的值
remove(node)
从列表中删除node并返回存储在其中的元素。
dllistnode对象
class llist.dllistnode([value])
返回一个新的双向链表节点，用value初始化（可选）。
dllistnode对象提供了以下属性：
next
列表中的下一个节点。 该属性是只读的。
prev
列表中的前一个节点。 该属性是只读的。
value
存储在此节点中的值。 从这个参考编译
sllist
class llist.sllist([iterable])返回一个新的llist.sllist([iterable])链表，用来自iterable元素初始化。 如果没有指定iterable，新的sllist是空的。
为这个sllist对象定义了一组类似的属性和操作。 有关更多信息，请参阅此参考。
双向链表的样例 （另存为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 （保存为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
这是我的解决scheme：
履行
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
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
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()
my double Linked List might be understandable to noobies.. If ur 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.
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
