python数据结构之链表

时间：2019-11-30 23:05:24 阅读：80 评论：0 收藏：0 [点我收藏+]

一、链表的基本结构

链表是通过一个个节点（Node）组成的，每个节点都包含了称为数据域(value)和指针域(next)的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。

技术分享图片

链表的基本元素有：

节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点
tail: tail永远指向最后一个节点
None:链表中最后一个节点的指针域为None值

二、链表的种类以及和动态数组(Array List)的对比

技术分享图片

  1 #先定义一个node的类
  2 calss Node():
  3     def _init_(self,value=None,next=None):
  4         self._value=value
  5         self._next=next
  6 
  7     def getValue(self):
  8         return self._value
  9     def getNext(self):
 10         return self._next
 11     def setValue(self,new_value):
 12         self._value=new_value
 13     def setNext(self,new_next):
 14         self._next=new_next
 15 
 16 
 17 
 18 #实现Linked List及其各类操作方法
 19 class LinkedList():
 20     def _init_(self):
 21         self._head=Node()
 22         self._tail=None
 23         self._length=0
 24 
 25     #检测是否为空
 26     def isEmpty(self):
 27         return self._head==None
 28     #add在链表前端添加元素：O(1)
 29     def add(self,value):
 30         newnode=Node(value,None)
 31         newnode.setNext(self._head)
 32         self._head=newnode
 33     #append在链表尾部添加元素：O（n）
 34     def append(self,value):
 35         newnode=Node(value)
 36         if self.isEmpty():
 37             self._head=newnode
 38         else:
 39             current=self._head
 40             while current.getNext()!=Node:
 41                 current=current.getNext()
 42             current.setNext(newnode)
 43 
 44 
 45 #search检索元素是否在链表中
 46 def search(self,value):
 47     current=self._head
 48     foundvalue=False
 49     while current != None and not foundvalue:
 50         if current.getValue()==value:
 51             foundValue=True
 52         else:
 53             current=current.getNext()
 54     return foundvalue
 55 
 56 #index索引元素在链表中的位置
 57 def index(self,value):
 58     current=self._head
 59     count=0
 60     found=None
 61     while current != None and not found:
 62         if current.getValue()==value:
 63             found=True
 64         else:
 65             current=current.getNext()
 66     if found:
 67         return count
 68     else:
 69         print("error")
 70 
 71 
 72 
 73 #remove删除链表中的某项元素
 74 def remove(self,value):
 75     current=self._head
 76     pre=None
 77     while current!=None:
 78         if current.getValue()==value:
 79             if not pre:
 80                 self._head=current.getNext()
 81             else:
 82                 pre.setNext(current.getNext())
 83             break
 84         else:
 85             pre=current
 86             current=current.getNext()
 87 
 88 #insert链表中插入元素
 89 def insert(self,pos,value):
 90     if pos<=1:
 91         self.add(value)
 92     elif pos>self.size():
 93         self.append(value)
 94     else:
 95         temp=Node(value)
 96         count=1
 97         pre=None
 98         current=self._head
 99         while count<pos:
100             count+=1
101             pre=current
102             current=current.getNext()
103         pre.setNext(temp)
104         temp.setNext(current)
105         
106