[数据结构与算法] 链接表总结
上一次说到了顺序表，链接表和顺序表一样，也是线性表。那为什么有了线性表还要有链接表呢？总之就是当数据过大时，顺序表存在一些存储方面的限制，而链接表比顺序表要更有效。链接表的主要不同之处在于使用了链接技术，那什么是链接技术？请看下面这个图
这个图是最简单的链接表，叫做单向链表，每一个位置上都存储着该位置的节点信息以及下一个位置的地址。就好像通过地址把顺序表的前一元素和后一元素链接起来了，所以叫链接技术。顺序表中前后元素也有关系，链接表和顺序表的区别是显式的而非隐式把这种关系表达出来。
这样做的好处是把表中元素都独立的存储在存储块中，这个存储块也叫表的节点。还有这样可以从表的任一个节点都可以找到与其关联的下一个节点。
下面开始具体说下单向链接表，也叫单链表或者链表
上面那个图就是一个单链表，单链表的结点是一个二元组，存储着值和下一个结点的标识，分别叫做值域和指针域，也叫元素域和链接域。单链表的结点之间通过结点链接建立起单向的顺序联系。单链表的结尾结点的链接域用空值来表示，在Python中就是None，有的语言里用0来表示。
下面我们开始说链接表的基本操作
创建空链表：要确定一个单链表，只要知道首结点就行，知道了首结点，就知道了下一个结点的元素，依次类推。所以创建一个空链表，既然为空，那就一个元素也没有，所以它的首元素的链接域也是一个空链接。
删除链表：要删除一个链表需要把链表中的元素全部删除，在Python中，只需要将表指针赋值为None，Python解释器的存储管理系统会自动回收不用的存储。
判断表是否为空：将表头变量的值与空链接比较，因为一个空链表的表头变量的值为空None，所以通过与空链接比较，就可以判断是否为空表。
判断表是否为满：顺序表在定义的时候，就会给定元素的最大存储数目，所以判断满很简单，就看元素个数是否等于最大存储数目。而链接不一样，一般来说，不存在满的链接表，除非数据占满了整个存储空间。
添加元素：给链表加入元素同样具有插入位置的问题，但是在链接表里面插入元素不需要对元素进行移动。因为插入新元素的操作是通过修改链接，接入到新的结点，从而改变了原来的表结构来实现的。
然后我们分别看一下，在表首端插入，在指定位置插入是怎么实现的。
表首端插入：插入新元素称为表的第一个元素。分三步来做，首先创建一个新结点并存入数据。注意这里只是创建了结点，和原链表并没有关系。然后把原链表首结点的链接存入刚才创建的结点的链接域。最后修改表头变量，使得表头变量指向新结点。简单用代码来表示一下这个过程就是：
q=LNode()
q.next = head.next
head=q一般情况的元素插入：要想在单链接表里某位置插入一个新结点，必须找到该位置之前的那个结点，因为新结点需要插入在它的后面。需要修改它的链接域。我们也分三步来完成这个操作，首先创建一个新结点并存入数据。然后把前一元素的链接域指向新结点的链接域，最后修改前一元素的链接域，使之指向新结点。用代码来表示就是：
q=LNode()
q.next = pre.next
pre.next=q删除元素： 删除元素和增加元素的原理是类似的，如果是删除首结点，只需要修改表头指针，令其指向第二个结点。丢弃不用的结点将被Python自动回收。删除其他位置的元素，需要修改上一个元素的链接域，使其指向下一个结点。这样中间这个元素就被删除了。
下面是一个链表的Python实现，首先定义结点类，然后定义链表类，以及各种操作的实现。
# - * - coding:utf-8 - * -
class LNode:
def __init__(self, x, next_=None):
self.elem=x
self.next=next_
class LList:
def __init__(self):
self._head=None
def is_empty(self):
return self._head is None
def prepend(self, elem):
self._head=LNode(elem, self._head)
def pop(self):
if self._head is None:
raise ValueError("in pop")
e = self._head.elem
self._head=self._head.next
print("head is :%s"%self._head)
return e
# 后端操作
def append(self,elem):
if self._head is None:
self._head = LNode(elem)
return
p = self._head
while p.next is not None:
p=p.next
p.next=LNode(elem)
def pop_last(self):
if self._head is None:
raise ValueError("in pop_last")
p = self._head
if p.next is None:
e=p.elem
self._head=None
return e
while p.next.next is not None:
p=p.next
e=p.next.elem
p.next=None
return e
def find(self, pred):
p=self._head
while p is not None:
if pred(p.elem):
return p.elem
p=p.next
def printall(self):
p=self._head
while p is not None:
if p.next is not None:
print(', ')
p=p.next
if __name__=="__main__":
node = LNode(elem=1, next_=2)
print(node)
mlist1 = LList()
for i in range(5):
mlist1.prepend(i)
print(mlist1.is_empty())
for i in range(15, 20):
mlist1.append(i)
mlist1.pop()
mlist1.printall()链表先到这里吧，看得我头疼，这点东西，搞了好几天。下次举几个链表的题目，通过例题理解的能深入一点。