Python单链表的简单实现方法，python单链实现

Python单链表的简单实现方法，python单链实现

本文实例讲述了Python单链表的简单实现方法，分享给大家供大家参考。具体方法如下：

通常来说，要定义一个单链表,首先定义链表元素:Element.它包含3个字段:

list:标识自己属于哪一个list
datum:改元素的value
next:下一个节点的位置

具体实现代码如下：

class LinkedList(object):
  
  class Element(object):
    
    def __init__(self,list,datum,next): 
      self._list = list
      self._datum = datum 
      self._next = next

    def getDatum(self): 
      return self._datum

    datum = property(
      fget = lambda self: self.getDatum())

    def getNext(self):
      return self._next

    next = property(
      fget = lambda self: self.getNext())

  def __init__(self):

    self._head = None
    self._tail = None
  def getHead(self):
    return self._head 
  head = property(
    fget = lambda self: self.getHead()) 
  def prepend(self,item):
    tmp = self.Element (self,item,self._head)
    if self._head is None:
      self._tail = tmp 
    self._head = tmp 

  def insert(self, pos, item):
    i = 0
    p = self._head
    while p != None and i < pos -1:
      p = p._next
      i += 1
    if p == None or i > pos-1:
      return -1
    tmp = self.Element(self, item, p._next)
    p._next = tmp
    return 1
  def getItem(self, pos):
    i = 0
    p = self._head
    while p != None and i < pos -1:
      p = p._next
      i += 1
    if p == None or i > post-1:
      return -1
    return p._datum
  def delete(self, pos):
    i = 0
    p = self._head
    while p != None and i < pos -1:
      p = p._next
      i += 1
    if p == None or i > post-1:
      return -1
    q = p._next
    p._nex = q._next
    datum = p._datum
    return datum
  def setItem(self, pos, item):
    i = 0
    p = self._head
    while p != None and i < pos -1:
      p = p._next
      i += 1
    if p == None or i > post-1:
      return -1
    p._datum = item
    return 1
  def find(self, pos, item):
    i = 0
    p = self._head
    while p != None and i < pos -1:
      if p._datum == item:
        return 1
      p = p._next
      i += 1
    return -1
  def empty(self):
    if self._head == None:
      return 1
    return 0
  def size(self):
    i = 0
    p = self._head
    while p != None and i < pos -1:
      p = p._next
      i += 1
    return i

  def clear(self):
    self._head = None
    self._tail = None

test = LinkedList()
test.prepend('test0')
print test.insert(1, 'test')
print test.head.datum
print test.head.next.datum

希望本文所述对大家的Python程序设计有所帮助。

Node没什么问题，就是变量定义的时候是一个下划线而不是两个
Stack这里有点问题，
（不知道你这里为啥需要做成一个循环的链表，不过不管了）
首先你得定义一个head和一个tail，这样的话才能把tail和head连接形成一个循环
初始化Stack的话把head和tail都设置成None表示这是个空的stack
push的话看你喜欢这么写了，比较喜欢的是把push进去的Node作为新的head，然后修改一下self._head为新Node，然后修改新Node的next为老的head，再连接一下Tail和Head便可，这样就省掉一些循环
pop的话就加一些判定好了，首先看Head是不是None，如果是就说明Stack是空的。如果发现Tail和Head都是同一个的话就说明Stack里就一项了，提取完Head之后就设置Stack为空吧。然后先提取Head，然后读取Head后面的那一个Node并且设置为新的Head，然后再连接一下Tail和Head便可
附上代码供参考.
class Node: def __init__(self, newData): self._data = newData self._next = None def getData(self): return self._data def getNext(self): return self._next def setData(self, newData): self._data = newData def setNext(self, newNode): self._next = newNodeclass Stack: def __init__(self): self._head = None self._tail = None def push(self, data): print 'Push',data,'into stack' new = Node(data) cur = self._head end = self._tail if cur is None: self._head = new new.setNext(new) self._tail = new else: new.setNext(self._head) self._head = new self._tail.setNext(new) def pop(self): if self._head is not None: cur = self._head print 'pop',cur.getData(),'out of stack' if cur.getNext() is not cur: self._head = cur.getNext() self._tail.setNext(self._head) else: ......余下全文>>
 

问题好乱！
一、getnext、setnext
这两个函数再明白不过了，设计者在类package中定义了一个package* pnext；用来指向链表的下一个元素，getnext就是要取得下一个元素，自然返回该指针，setnext就是要给当前元素指定其下一个元素的地址，自然是给pnext赋值。

二、在创建第一个package对象时，pnext初始化为0，那么在创建第二个package对象时，第一个package对象中的pnext是如何指向它的（不是已经初始化为0了么？）？
看这段代码：
package* ppackage= new package(pBox);

if (pHead)
pTail->setnext(ppackage);

先创建第二个package对象，然后pTail->setnext(ppackage);
注意pTail永远指向链表的最后一个对象，因此pTail->setnext(ppackage);的意思是将第二个对象是放在了第一个对象的pnext中，也就将第一个对象和第二个对象链接起来了。

三、若把当次创建的package对象的地址ppackage赋予给pnext,那么pnext 不是指向刚刚创建的对象了么？好像并没有指向下一个package对象啊？
正如上面所说，setnext是把刚刚创建的对象放到当前链表最后一个元素的pnext成员里，在此之前，刚刚创建的对象还不在链表中，链表的最后一个元素是上次创建的那个。

四、还有到最后，如何使pnext为0？
你也说了，pnext在package创建的时候就赋值为0的，因此不需要再给最后一个package的pnext赋值0。