浅谈Python单向链表的实现

链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头。

删除操作可以通过修改一个指针来实现。

插入操作需要执行两次指针调整。

1. 单向链表的实现

1.1 Node实现

每个Node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个Node。

    class Node():
      __slots__=['_item','_next']  #限定Node实例的属性
      def __init__(self,item):
        self._item=item
        self._next=None   #Node的指针部分默认指向None
      def getItem(self):
        return self._item
      def getNext(self):
        return self._next
      def setItem(self,newitem):
        self._item=newitem
      def setNext(self,newnext):
        self._next=newnext

1.2 SinglelinkedList的实现

    class SingleLinkedList(): 
      def __init__(self):
        self._head=None  #初始化链表为空表
        self._size=0

1.3 检测链表是否为空

    def isEmpty(self):
      return self._head==None 

1.4 add在链表前端添加元素

    def add(self,item):
      temp=Node(item)
      temp.setNext(self._head)
      self._head=temp

1.5 append在链表尾部添加元素

    def append(self,item):
      temp=Node(item)
      if self.isEmpty():
        self._head=temp  #若为空表，将添加的元素设为第一个元素
      else:
        current=self._head
        while current.getNext()!=None:
          current=current.getNext()  #遍历链表
        current.setNext(temp)  #此时current为链表最后的元素

1.6 search检索元素是否在链表中

    def search(self,item):
      current=self._head
      founditem=False
      while current!=None and not founditem:
        if current.getItem()==item:
          founditem=True
        else:
          current=current.getNext()
      return founditem

1.7 index索引元素在链表中的位置

    def index(self,item):
      current=self._head
      count=0
      found=None
      while current!=None and not found:
        count+=1
        if current.getItem()==item:
          found=True
        else:
          current=current.getNext()
      if found:
        return count
      else:
        raise ValueError,'%s is not in linkedlist'%item

1.8 remove删除链表中的某项元素

    def remove(self,item):
      current=self._head
      pre=None
      while current!=None:
        if current.getItem()==item:
          if not pre:
            self._head=current.getNext()
          else:
            pre.setNext(current.getNext())
          break
        else:
          pre=current
          current=current.getNext()

1.9 insert链表中插入元素

    def insert(self,pos,item):
      if pos<=1:
        self.add(item)
      elif pos>self.size():
        self.append(item)
      else:
        temp=Node(item)
        count=1
        pre=None
        current=self._head
        while count<pos:
          count+=1
          pre=current
          current=current.getNext()
        pre.setNext(temp)
        temp.setNext(current)

全部代码

    class Node():
      __slots__=['_item','_next']
      def __init__(self,item):
        self._item=item
        self._next=None
      def getItem(self):
        return self._item
      def getNext(self):
        return self._next
      def setItem(self,newitem):
        self._item=newitem
      def setNext(self,newnext):
        self._next=newnext

    class SingleLinkedList(): 
      def __init__(self):
        self._head=None #初始化为空链表
      def isEmpty(self):
        return self._head==None
      def size(self):
        current=self._head
        count=0
        while current!=None:
          count+=1
          current=current.getNext()
        return count
      def travel(self):
        current=self._head
        while current!=None:
          print current.getItem()
          current=current.getNext()
      def add(self,item):
        temp=Node(item)
        temp.setNext(self._head)
        self._head=temp

      def append(self,item):
        temp=Node(item)
        if self.isEmpty():
          self._head=temp  #若为空表，将添加的元素设为第一个元素
        else:
          current=self._head
          while current.getNext()!=None:
            current=current.getNext()  #遍历链表
          current.setNext(temp)  #此时current为链表最后的元素
      def search(self,item):
        current=self._head
        founditem=False
        while current!=None and not founditem:
          if current.getItem()==item:
            founditem=True
          else:
            current=current.getNext()
        return founditem
      def index(self,item):
        current=self._head
        count=0
        found=None
        while current!=None and not found:
          count+=1
          if current.getItem()==item:
            found=True
          else:
            current=current.getNext()
        if found:
          return count
        else:
          raise ValueError,'%s is not in linkedlist'%item       
      def remove(self,item):
        current=self._head
        pre=None
        while current!=None:
          if current.getItem()==item:
            if not pre:
              self._head=current.getNext()
            else:
              pre.setNext(current.getNext())
            break
          else:
            pre=current
            current=current.getNext()           
      def insert(self,pos,item):
        if pos<=1:
          self.add(item)
        elif pos>self.size():
          self.append(item)
        else:
          temp=Node(item)
          count=1
          pre=None
          current=self._head
          while count<pos:
            count+=1
            pre=current
            current=current.getNext()
          pre.setNext(temp)
          temp.setNext(current)

    if __name__=='__main__':
      a=SingleLinkedList()
      for i in range(1,10):
        a.append(i)
      print a.size()
      a.travel()
      print a.search(6)
      print a.index(5)
      a.remove(4)
      a.travel()
      a.insert(4,100)
      a.travel()