链表的定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，每个结点包括两个部分：一个是存储数据元素的数据域，一个是存储下一个节点地址的指针域。
由于不必按照顺序存储，链表在插入的时候可以达到O(1)的复杂度，但是查找的时候则需要O(n)的时间复杂度，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
分类
单向链表
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单链表.png
新增节点.png
删除节点
代码实现
class SingleLinkedList {
private var size:Int = 0
private var head: Node? = null//头节点
val isEmpty:Boolean//判断链表是否为空
get() = size==0
init {
size=0
head=null
}
class Node(var data:Any){//每个节点数据
var next:Node?=null//每个节点指向的下一个节点地址
}
//在表头添加元素
fun addHead(obj:Any):Any{
var newHead=Node(obj)
if(size==0){
head=newHead
}else{
newHead.next=head
head=newHead
}
size++
return obj
}
//在链表头删除元素
fun deleteHead():Any{
val obj=head!!.data
head=head!!.next
size--
return obj
}
//查找指定元素，找到了返回节点Node,找不到返回null
fun find(obj:Any):Node?{
var current=head
var tempSize=size
while (tempSize>0){
if(obj==current!!.data){
return current
}else{
current=current.next
}
tempSize--
}
return null
}
//删除指定元素，删除成功返回true
fun delete(value: Any):Boolean{
if(size==0){
return false
}
var current=head
var previous=head
while (current!!.data!=value){
if(current.next==null){
return false
}else{
previous=current
current=current.next
}
}
if(current==head){//如果删除的节点是第一个节点
head= current.next
size--
}else{
previous!!.next=current.next
size--
}
return true
}
//显示节点信息
fun display():String{
if(size>0){
var node=head
var tempSize=size
var str=StringBuffer()
if(tempSize==1){//当前链表只有一个节点
return "["+node!!.data+"]"
}
while (tempSize>0){
if(node==head){//第一个元素
str.append("[").append(node!!.data).append("->")
}else if(node!!.next==null){//最后一个元素
str.append(node.data).append("]")
}else{
str.append(node.data).append("->")
}
node=node.next
tempSize--
}
return str.toString()
}else{
return "[]"
}
}
}
具体的调用方法
override fun onClick(v: View?) {
when(v!!.id){
R.id.tvAdd->{//添加
singleList.addHead("A")
singleList.addHead("B")
singleList.addHead("C")
singleList.addHead("D")
}
R.id.tvFind->{//查找
tvResult.text="结果："+singleList.find("B")!!.data
singleList.find("C")
}
R.id.tvDisplay->{//展示
tvResult.text="结果："+singleList.display()
}
R.id.tvDelete->{//删除
singleList.delete("B")
}
}
}
双端链表
双端链表与单链表十分相似，不同的是它新增一个对尾结点的引用。双端链表不是双向链表
双端链表
class DoublePointLinkedList {
private var head:Node?=null//头节点
private var tail:Node?=null//尾节点
var size:Int=0//链表节点数
private set
val isEmpty:Boolean
get() = size==0
class Node(var data:Any){
var next:Node?=null
}
init {
size=0
head=null
tail=null
}
//链表头新增节点
fun addHead(data:Any){
val node=Node(data)
if(size==0){//如果链表为空，那么头节点和尾节点都是该新增节点
head=node
tail=node
size++
}else{
node.next=head
head=node
size++
}
}
//链表尾新增节点
fun addTail(data:Any){
val node=Node(data)
if(size==0){//如果链表为空，那么头节点和尾节点都是该新增节点
head=node
tail=node
size++
}else{
tail!!.next =node
tail=node
size++
}
}
//删除头部节点，成功返回true，失败返回false
fun deleteHead():Boolean{
if(size==0){
return false
}
if (head!!.next==null){//当前链表节点数为1
head=null
tail=null
}else{
head=head!!.next
}
size--
return true
}
//显示节点信息
fun display():String{
var str=StringBuffer()
if(size>0){
var node=head
var tempSize=size
if(tempSize==1){//当前链表只有一个节点
str.append("[").append(node!!.data.toString()).append("]")
return str.toString()
}
while (tempSize>0){
if(node==head){
str.append("[").append(node!!.data.toString()).append("->")
}else if(node!!.next==null){
str.append(node!!.data.toString()).append("]")
}else{
str.append(node!!.data.toString()).append("->")
}
node=node.next
tempSize--
}
}else{
str.append("[]")
}
return str.toString()
}
}
具体调用就不写了，和上面差不多
双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向链表
具体代码实现：
class TwoWayLinkedList{
private var head:Node?=null
private var tail:Node?=null
var size:Int=0//获得链表的节点个数
private set
val isEmpty:Boolean//判断链表是否为空
get() = size==0
class Node(val data:Any){
var next:Node?=null
var prev:Node?=null
}
init {
head=null
tail=null
size=0
}
//在链表头增加节点
fun addHead(data:Any){
val newNode=Node(data)
if(size==0){
head=newNode
tail=newNode
size++
}else{
head!!.prev=newNode
newNode.next=head
head=newNode
size++
}
}
//在链表尾增加节点
fun addTail(data:Any){
val newNode=Node(data)
if(size==0){
head=newNode
tail=newNode
size++
}else{
newNode.prev=tail
tail!!.next=newNode
tail=newNode
size++
}
}
//删除链表头
fun deleteHead(): Node? {
val temp=head
if(size!=0){
head=head!!.next
head!!.prev=null
size--
}
return temp
}
//删除链表尾
fun deleteTail():Node?{
val temp=tail
if(size!=0) {
tail=tail!!.prev
tail!!.next=null
size--
}
return temp
}
//显示节点信息
fun display():String{
var str=StringBuffer()
if(size>0){
var node=head
var tempSize=size
if(tempSize==1){
str.append("[").append(node!!.data).append("]")
return str.toString()
}
while (tempSize>0){
if(node==head){
str.append("[").append(node!!.data.toString()).append("->")
}else if(node!!.next==null){
str.append(node!!.data.toString()).append("]")
}else{
str.append(node!!.data.toString()).append("->")
}
node=node.next
tempSize--
}
}else{
str.append("[]")
}
return str.toString()
}
}
典型案例：
1.合并两个有序链表(LeetCode第21题)
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
class Solution {
ListNode(var `val`: Int) {
var next: ListNode? = null
}
fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
var mL1=l1
var mL2=l2
if (mL1==null){//判断l1是否为空，如果为空，返回l2
return l2
}else if(mL2==null){//判断l2是否为空，如果为空，返回l1
return l1
}else if(mL1.`val`<mL2.`val`){//判断l1和l2哪个头元素更小
mL1.next=mergeTwoLists(mL1.next,mL2)
return mL1
}else{
mL2.next=mergeTwoLists(mL2.next,mL1)
return mL2
}
}
}
2.回文链表(LeetCode第234题)
请判断一个链表是否为回文链表
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
题解：双指针
定义两个指针，fast指针每次走两步，slow指针每次走一步
fast指针走到链表末尾的时候，slow指针走到链表的中间位置结点（链表长度n为偶数）或中间位置的前一个结点（链表长度n为奇数）
fun isPalindrome(head: ListNode?): Boolean {
//双指针
var mHead=head
if(mHead==null || mHead!!.next==null){//判断是否为空
return true
}
//定义两个指针，fast指针每次走两步，slow指针每次走一步
var fast=mHead.next!!.next
var slow=mHead.next
while (fast?.next != null){
fast= fast.next!!.next
slow=slow!!.next
}
//翻转链表前半部分(以slow为界)
var pre:ListNode?=null
var next:ListNode?=null
while (mHead!=slow){
next=mHead!!.next
mHead.next=pre
pre=mHead
mHead=next
}
//如果是奇数个节点，去掉后半部分的第一个节点
if(fast!=null){
slow=slow.next
}
//回文校验
while (pre!=null){
if(pre.`val`!=slow!!.`val`){
return false
}
pre= pre.next
slow=slow.next
}
return true
}
