链表的定义：链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结点。链表中的最后一个结点没有后继元素，其指针域为空。
python单链表实现代码：
代码如下:
#!/usr/bin/python# -*- coding: utf-8 -*-
class node(object): def __init__(self,val,p=0): self.data = val self.next = 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 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 self.getlength(): print ‘the given key is error’ return
else: self.delete(key) return self.insert(key)
def initlist(self,data):
self.head = node(data[0])
p = self.head
for i in data[1:]: node = node(i) p.next = node p = p.next
def getlength(self):
p = self.head length = 0 while p!=0: length+=1 p = p.next
return length
def is_empty(self):
if self.getlength() ==0: return true else: return false
def clear(self):
self.head = 0
def append(self,item):
q = node(item) if self.head ==0: self.head = q else: p = self.head while p.next!=0: p = p.next p.next = q
def getitem(self,index):
if self.is_empty(): print ‘linklist is empty.’ return j = 0 p = self.head
while p.next!=0 and j