提高链表的查询效率

链表是增删快，查询慢的数据结构，那么怎么提高其的查询效率呢？
1、参考LRU问题，可以在链表的基础上加一个hashmap
2、参考redis中的跳表结构，其实现大概就是给链表加索引，但是要保证链表有序

  1. class Node:
  2.     '''
  3.     data: 节点保存的数据
  4.     _next: 保存下一个节点对象
  5.     '''
  6.     def __init__(self, data, pnext=None):
  7.         self.data = data
  8.         self._next = pnext
  10.     def __repr__(self):
  11.         '''
  12.         用来定义Node的字符输出，
  13.         print为输出data
  14.         '''
  15.         return str(self.data)

然后，定义链表类：
链表要包括：
属性：
链表头：head
链表长度：length
方法：
判断是否为空: isEmpty()

  1. def isEmpty(self):
  2.     return (self.length == 0

增加一个节点(在链表尾添加): append()

  1. def append(self, dataOrNode):
  2.     item = None
  3.     if isinstance(dataOrNode, Node):
  4.         item = dataOrNode
  5.     else:
  6.         item = Node(dataOrNode)
  8.     if not self.head:
  9.         self.head = item
  10.         self.length += 1
  12.     else:
  13.         node = self.head
  14.         while node._next:
  15.             node = node._next
  16.         node._next = item
  17.         self.length += 1

删除一个节点: delete()

#删除一个节点之后记得要把链表长度减一
def delete(self, index):
    if self.isEmpty():
        print "this chain table is empty."
        return

    if index < 0 or index >= self.length:
        print 'error: out of index'
        return
    #要注意删除第一个节点的情况
    #如果有空的头节点就不用这样
    #但是我不喜欢弄头节点
    if index == 0:
        self.head = self.head._next
        self.length -= 1
        return

    #prev为保存前导节点
    #node为保存当前节点
    #当j与index相等时就
    #相当于找到要删除的节点
    j = 0
    node = self.head
    prev = self.head
    while node._next and j < index:
        prev = node
        node = node._next
        j += 1

    if j == index:
        prev._next = node._next
        self.length -= 1

# 修改一个节点: update()
def update(self, index, data):
    if self.isEmpty() or index < 0 or index >= self.length:
        print 'error: out of index'
        return
    j = 0
    node = self.head
    while node._next and j < index:
        node = node._next
        j += 1

    if j == index:
        node.data = data

# 查找一个节点: getItem()        
def getItem(self, index):
    if self.isEmpty() or index < 0 or index >= self.length:
        print "error: out of index"
        return
    j = 0
    node = self.head
    while node._next and j < index:
        node = node._next
        j += 1

    return node.data

# 查找一个节点的索引: getIndex()
def getIndex(self, data):
    j = 0
    if self.isEmpty():
        print "this chain table is empty"
        return
    node = self.head
    while node:
        if node.data == data:
            return j
        node = node._next
        j += 1

    if j == self.length:
        print "%s not found" % str(data)
        return

# 插入一个节点: insert()    

def insert(self, index, dataOrNode):
    if self.isEmpty():
        print "this chain tabale is empty"
        return

    if index < 0 or index >= self.length:
        print "error: out of index"
        return

    item = None
    if isinstance(dataOrNode, Node):
        item = dataOrNode
    else:
        item = Node(dataOrNode)

    if index == 0:
        item._next = self.head
        self.head = item
        self.length += 1
        return

    j = 0
    node = self.head
    prev = self.head
    while node._next and j < index:
        prev = node
        node = node._next
        j += 1

    if j == index:
        item._next = node
        prev._next = item
        self.length += 1


# 清空链表: clear()      
def clear(self):
    self.head = None
    self.length = 0