python版本单链表实现代码
今天看了一下数据结构的书，发现其实数据结构没有几种，线性表，数组，字符串，队列和栈，等等，其实是一回事，然后就是树结构，图结构。数据结构的理论并不难，主要是要自己写一下这些数据结构以及对应的基本的操作方法，这样就能够更快的提高。
这一篇blog写一下线性表。
线性表：分为顺序表和链表
一、顺序表
顺序表就是相对于表中的数据，地址也是顺序的，所以可以随机存取。但是在操作插入和删除元素的时候，由于要满足地址的连续性，所以要移动很多的元素位置，因此，插入或者删除一个顺序表的元素的时间复杂度是o(n)。很多时候，在对顺序表做合并的时候，需要先对表中的元素进行排序，然后再进行处理，这样可以避免每次都从头进行查询。
二、链表
链表就失去了顺序表的随机存取特点，即每次从中取一个元素都要从头开始找，这样耗费了一些时间，时间复杂度为o(n)；但是在做插入和删除，以及两个链表合并的时候，就方便了很多，只需要做一点指针修改就可以了。
链表中的每一个元素节点都包含了数据部分和下一个节点的指针。一般在链表的头部附设一个头结点，而且头结点一般不存储数据，而是存放一些长度等附加信息，或者不存储。
在很多语言中没有指针这一概念，而有数组的概念，比如java和python，java中的数组还要求定义数组的类型，也就是说必须都是同一类型的数据，而python则没有要求，所以python的list更贴近链表的真正含义。这种用数组描述的链表叫做静态链表。使用静态链表来描述链表对此类语言要方便很多了，本身这些语言都提供了内置类来处理链表。
除此之外，还有循环链表，双向链表（解决了无法向前搜索的问题，但是在修改指针的时候需要有更多的操作）。
#-*-coding=utf-8-*- #这个例子是Python版本的单链表 classNode(object): def__init__(self,value,next=0): self.value=value self.next=next#指针 classLinkedList(object): #链表的数据结构 def__init__(self): self.head=0#头部 def__getitem__(self,key): ifself.is_empty(): print'Linkedlistisempty.' return elifkey<0orkey>self.get_length(): print'Thegivenkeyiswrong.' return else: returnself.get_elem(key) def__setitem__(self,key,value): ifself.is_empty(): print'Linkedlistisempty.' return elifkey<0orkey>self.get_length(): print'Thegivenkeyiswrong.' return else: returnself.set_elem(key,value) definit_list(self,data):#按列表给出data self.head=Node(data[0]) p=self.head#指针指向头结点 printp,self.head foriindata[1:]: p.next=Node(i)#确定指针指向下一个结点 p=p.next#指针滑动向下一个位置 printself.head.next.next defget_length(self): length=0 p=self.head whilep!=0:#0值就是Node结点中默认的0值，表示下一个结点没有了，即没有为其赋值 length+=1 p=p.next returnlength defis_empty(self): ifself.head==0: returnTrue else: returnFalse definsert_node(self,index,value): ifindex<0orindex>self.get_length(): print'Cannotinsertnodeintothelinkedlist.' elifindex==0: temp=self.head self.head=Node(value,temp) else: p,post=self.head,self.head foriinxrange(index): post=p p=p.next temp=p post.next=Node(value,temp) defdelete_node(self,index): ifindex<0orindex>self.get_length()-1: print"Wrongindexnumbertodeleteanynode." elifself.is_empty(): print"Nonodecanbedeleted." elifindex==0: temp=self.head self.head=temp.next elifindex==self.get_length(): p=self.head foriinxrange(self.get_length()-2): p=p.next p.next=0 else: p=self.head foriinxrange(index-1): p=p.next p.next=p.next.next defshow_linked_list(self):#打印链表中的所有元素 ifself.is_empty(): print'Thisisanemptylinkedlist.' else: p,container=self.head,[] for_inxrange(self.get_length()-1): container.append(p.value) p=p.next container.append(p.value) printcontainer defclear_linked_list(self):#将链表置空 self.head=0 defget_elem(self,index): ifself.is_empty(): print"Thelinkedlistisempty.Cannotgetelement." elifindex<0orindex>self.get_length()-1: print"Wrongindexnumbertogetanyelement." else: p=self.head for_inxrange(index): p=p.next returnp.value defset_elem(self,index,value): ifself.is_empty(): print"Thelinkedlistisempty.Cannotsetelement." elifindex<0orindex>self.get_length()-1: print"Wrongindexnumbertosetelement." else: p=self.head for_inxrange(index): p=p.next p.value=value defget_index(self,value): p=self.head foriinxrange(self.get_length()): ifp.value==value: returni else: p=p.next return-1 l=LinkedList() print"Thelengthoflinkedlistnowis:",l.get_length() printl.is_empty() l.init_list([1,5,12,"fjd",45,999]) print"Thelengthoflinkedlistnowis:",l.get_length() printl.is_empty() l.insert_node(4,100) l.insert_node(6,"cecil") l.show_linked_list() print"Thevalueofindex0is:",l.get_elem(0) l.set_elem(0,1000) l.show_linked_list() print"theindexof***is:",l.get_index(1009) print"Thelengthoflinkedlistnowis:",l.get_length() l.delete_node(3) #l.clear_linked_list() l.show_linked_list()
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。