搞懂单链表

学习目标

• 单链表的定义
• 单链表的增删改查操作
• 链表的经典算法题
• 链表的实际应用场景

1.什么是单链表

单链表是一种常见的基础数据结构，本质是线性表的链式存储方式中的一种。链表不需要像数组那样将数据存储在一个连续的内存中，而是在每个链表节点中分配了一个数据域 ** 和一个指针域**，其中数据域用于存储数据，指针域用于存储下一个节点的地址。这样就无需在开辟一块连续的内存空间用来存储。

2.单链表的特点

• 对比数组，链表增删数据快，但是查询数据慢
• 单链表无需像数组那样预先分配存储空间的大小

3.单链表的基本操作

主要介绍单链表的一些属性和增删改查操作

3.1单链表的节点类定义

对于单链表中的一个节点采用下面的代码表示

//定义节点类
public class Node{//数据域int data;//指针域Node next;public Node(int data) {this.data = data;}@Overridepublic String toString() {return "Node{" +"data=" + data +", next=" + next +'}';}
}

3.2获取单链表的长度

单链表的存储地址并不是连续的，所以对于一个链表的长度只能通过遍历链表节点的方式获取，其中head为头节点。对于单链表的操作都需要从头节点开始，意味着如果头节点丢失的话，会导致整个链表丢失，所以定义好头节点之后，不要在上面进行操作，而是用一个临时变量temp来代替

//链表长度
public int getLength(Node head){int length = 0;Node temp = head;while (temp != null){length++;temp = temp.next;}return length;
}

3.3打印链表

//打印链表
public void printList(Node head){Node temp = head;if (temp == null){System.out.println("链表为空");return;}while (temp.next != null){System.out.println(temp);temp = temp.next;}
}

3.4添加元素

根据元素添加位置的不同，可以将添加元素操作分为头插法，尾插法，指定位置插入法。

3.4.1 头插法

头插法需要获取头节点，对于插入的新数据，都是先对其指针域先赋值，先将头节点原先的指针域赋给新节点的指针域，然后再让头节点指向新数据

//插入节点-头插法
public void addAtHead(Node head,Node node){node.next = head.next;head.next = node;
}

3.4.2尾插法

尾插法主要是需要找到尾节点，这里需从头节点开始一次遍历，当遍历到的节点的指针域为null时，那这个节点就是尾节点。

//插入节点-尾插法
public void addAtTail(Node head,Node node){Node temp = head;//找到尾节点while (temp.next != null){temp = temp.next;}temp.next = node;
}

3.4.3指定位置插入

先判断index是否在范围之内，然后再判断头插法和尾插法两种特殊插入方法，最后是从头节点遍历节点找到指定的节点，然后插入元素

//指定位置插入
public void insertElem(Node head,Node node,int index) throws Exception {int length = getLength(head);if (index < 0 || index >= length){throw new Exception("越界");}if (index == 0){addAtHead(head,node);}else if (index == length -1){addAtTail(head,node);}else {Node temp = head;//遍历找到指定节点while (index > 1){temp = temp.next;index--;}//找到指定节点后插入元素node.next = temp.next;temp.next = node;}
}

3.5查询元素

查询元素又分为根据元素的值进行查找和根据元素的index进行查找

3.5.1根据索引查找

主要还是从头节点开始遍历

//根据索引查找,返回值
public int searchIndexNode(Node head,int index) throws Exception {int length = getLength(head);if (index < 0 || index >= length){throw new Exception("越界");}Node temp = head;while (index > 1){temp = temp.next;index--;}return temp.data;
}

3.5.2 根据值查找

从头节点开始遍历

//根据值查找，返回索引，-1表示查询不到
public int searchNode(Node head, int value){int index = -1;Node temp = head;while (temp.next != null){index++;if (temp.data == value){return index;}temp = temp.next;}return -1;
}

3.6删除元素

根据元素的位置不同，可以分为删除第一个元素，删除尾节点和删除指定索引元素。注意删除元素后要进行元素的垃圾回收

3.6.1删除第一个元素

区分第一元素和头节点的概念

//删除第一个元素
public void deleteFirst(Node head) throws Exception {if (head == null){throw new Exception("链表为空");}if (head.next.next != null){Node temp = head.next.next;//垃圾回收head.next = null;//删除head.next = temp;}else {//垃圾回收head.next = null;}
}

3.6.2删除最后一个元素

//删除尾节点
public void deleteTail(Node head) throws Exception {if (head == null){throw new Exception("链表为空");}Node temp = head;while (temp.next != null && temp.next.next != null){temp = temp.next;}//垃圾回收temp.next.next = null;//删除节点temp.next = null;
}

3.6.3 删除指定索引元素

//删除指定索引的元素
public void deleteIndexElem(Node head,int index) throws Exception {int length = getLength(head);if (index < 0 || index >= length){throw new Exception("越界");}if (index == 0){deleteFirst(head);}else if (index == length - 1){deleteTail(head);}else {Node temp = head;while (index > 1){temp = temp.next;index--;}Node temp2 = temp.next.next;//垃圾回收temp.next = null;temp.next = temp2;}
}

4.单链表常见面试题

4.1 判断链表是否有环

别的问法：判断；链表是否是循环链表

考察知识点：快慢指针

解释：如果两个人在操场上跑步，A跑得快，B跑得慢，操场是环形的那么A和B一定会再次相遇，如果不是环形的，那么B一定追不上A

//判断是否有环
public boolean isLoopList(Node head){if (head == null){return false;}Node slow = head;Node fast = head;while (fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow){return true;}}return false;
}

未完持续
下次更新面试题以及单链表在实际的应用场景

注：仅用于学习交流