Python线性双链表的构建

1 问题

单链表在查找大量数据方面有一定的复杂与困难，计算量大，只能单方向的寻找数据，不能随意的查找结点数据。

2 方法

用文字描述解题思路，可配合一些图形以便更好的阐述。解决问题的步骤采用如下方式：

1. 结构中给出存储元素的位置，在建立两个指针，一个指向前驱结点，另一个指向后继结点；

2. 每个元素的前驱结点的指针指向前面的元素；

3. 头插法是双链表从头部依次插入元素，在单向链表的每个结点中再设置一个指向其前驱结点的指针域。

   即它有两个指针域，一个指向前驱，一个指向后继。

通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。

代码清单 1

class Node(object):
def __init__(self,val,p=0):
      self.data = val
      self.next = p
      self.prev = p
class LinkList(object):
   def __init__(self):
      self.head = 0
   def __getitem__(self, key):
       if self.is_empty():
          print 'linklist is empty.'
          return
       elif key <0 or key > self.getlength():
           print 'the given key is error'
           return
   else:
        return self.getitem(key)
 def __setitem__(self, key, value):
     if self.is_empty():
         print 'linklist is empty.'
         return
      elif key <0 or key > self.getlength():
          print 'the given key is error'
          return
      else:
           self.delete(key)
           return self.insert(key)  

3 结语

针对单链表查找大量数据时出现的困难，单链表其结构简单，功能少，通过单链表构建双链表，链式存储结构--链表不受固定的存储空间限制，可以快速进行插入和删除操作。