数据结构与算法之单向链表

心已赠人 2022-01-05 09:57 270阅读 0赞

## 前言 ##

**链表**是一中有序的线性列表，链表与数组不同的是，数组是一种连续存储的线性结构，而链表是以节点的形式来存储的。  
链表有分为好几类，分别是：

1.  单向链表：一个节点指向下一个节点
2.  双向链表：一个节点有两个指针域，分别指向前一个节点和后一个节点
3.  环形链表：能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环

此处先讲解`单向链表`，单向链表每个节点都包含`data域`和`next域`，`next域`是用来指向下一个节点，如果`next`节点为空，则代表此节点为最后一个节点。链表的各个节点在内存种分布的时候不一定是连续存储的，只是逻辑结构上是连续的。  
链表分为`带头节点的链表`和`不带头节点的链表`。

单向链表内存结构图：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70][]

单向链表逻辑结构图：  
![20190623182710543.png][]

## 单向链表实现 ##

下面我将使用代码来实现带头节点的单向链表,并实现以下功能：

*  增加
 *  删除
 *  修改
 *  获取链表长度
 *  查找
 *  链表反转
 *  显示链表数据

### 添加 ###

实现思路：

1.  定义一个头节点，代表链表头部
2.  定义一个临时变量，辅助遍历整个链表
3.  遍历整个链表，直到找到最后一个节点
4.  将最后一个节点的`next`指向新增的节点

public boolean add(T item){
        Node<T> newNode = new Node<>(item);
    
        Node<T> tempNode = head; // 将头节点赋值给临时节点
        while(tempNode.next != null){ // 遍历找到最后一个节点
            tempNode = tempNode.next;
        }
    
        tempNode.next = newNode; // 将最后一个节点的next指向新的节点
        return true;
    }

### 删除 ###

实现思路：

1.  先判断链表是否为空，为空的条件就是：`head.next = null`;
2.  遍历链表，找个需要删除的这个节点的前一个节点
3.  将需要删除的这个节点的前一个节点的`next`指向需要删除的这个节点的下一个节点： `tempNode.next = tempNode.next.next`
4.  被删除的这个节点将不会再被引用，垃圾回收机制会自动回收

public boolean remove(T item) {
        if (this.isEmpty()) {
            System.out.println("linkedList is empty");
            return false;
        }
    
        Node<T> tempNode = head; // 将头节点赋值给临时节点
        while (true) {
            if (tempNode.next == null) {
                System.out.println("node next is empty");
                break;
            }
            if (item.equals(tempNode.next.item)) {
                tempNode.next = tempNode.next.next;
                return true;
            }
            tempNode = tempNode.next;
        }
        System.out.println("not find node item");
        return false;
    }

### 修改 ###

实现思路：

1.  遍历链表，找到需要修改的节点
2.  将新的数据赋值给修改的节点

public boolean update(T sourceItem, T tragetItem) {
        if (this.isEmpty()) {
            System.out.println("linkedList is empty");
            return false;
        }
    
        Node<T> tempNode = head; // 将第一个节点赋值给临时节点
        while (true) {
            if (tempNode == null) {
                System.out.println("node is empty");
                break;
            }
            if (sourceItem.equals(tempNode.item)) {
                tempNode.item = tragetItem;
                return true;
            }
            tempNode = tempNode.next;
        }
    
        return false;
    }

### 获取链表长度 ###

实现思路：

1.  遍历链表，每得到一个节点，size+1

public int size() {
        if (this.isEmpty()) {
            return 0;
        }
    
        int size = 0;
        Node<T> tempNode = head; // 将头节点赋值给临时节点
        while (tempNode.next != null) { // 遍历找到最后一个节点
            size++;
            tempNode = tempNode.next;
        }
    
        return size;
    }

### 查找（查找单链表中的倒数第k个结点） ###

实现思路：

1.  先做基础校验，链表为空、下标小于等于0、下标大于链表长度等都返回空
2.  获取链表长度
3.  遍历链表，总共遍历`size - index`次，就可以得到倒数第k个节点，比如说链表长度为5要获取倒数第一个节点，那么就是5-1 = 4，第四个节点就是倒数第1个节点

public Node<T> findLastIndexNode(int index){
        if(this.isEmpty()){
            return null;
        }
    
        int size = this.size(); // 获取链表长度
        if(index <= 0 || index > size){
            return null;
        }
    
        Node<T> tempNode = head.next; // 将第一个有效节点赋值给临时变量
        for (int i = 0; i < size - index; i++) {
            tempNode = tempNode.next;
        }
    
        return tempNode;
    }

### 链表反转 ###

实现思路：

链表反转有两种实现方式，一种是递归反转，一种是非递归反转，两种方式的操作顺序不太一样。

非递归反转：

非递归反转，是从链表头部第一个有效节点开始，依次遍历，替换当前节点的下一节点为前一个节点  
反转示意图：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70 1][]

public Node<T> reverseLinkList() {
        // 如果当前链表为空或者只有一个节点，则无需反转，直接返回
        if (this.isEmpty() || head.next.next == null) {
            return head;
        }
    
        Node<T> tempNode = head.next; // 将第一个有效节点赋值给临时变量
        Node<T> prev = null; // 临时变量前一个节点
        while (tempNode != null) {
            Node<T> next = tempNode.next; // 当前节点的下一个节点
            Node<T> currentNode = tempNode; // 当前遍历的节点
            // 将前一个节点赋值给当前节点的下一个节点(此处是进行节点反转)
            // 比如有a、b、c、d、e等5个几点，那第一个节点为a
            // 进行反转的话，a就成了最后一个节点，所以a的next = prev（当遍历第一个节点的时候，prev就等于null）
            // 遍历第二个节点b的时候，b的next就是prev，前一个节点为a，所以b就到了a的前面
            // 后面依次遍历
            currentNode.next = prev;
            // 将当前节点赋值给临时变量 -> 前一个节点
            prev = currentNode;
            tempNode = next; // 往后移动一个节点（a -> b）
        }
        return prev;
    }

递归反转：  
递归反转是从链表尾部节点开始

反转示意图：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70 2][]

public Node<T> recursionReverseLinkList() {
        // 如果当前链表为空或者只有一个节点，则无需反转，直接返回
        if (this.isEmpty() || head.next.next == null) {
            return head;
        }
        return recursionReverse(head);
    }
    
    public Node<T> recursionReverse(Node<T> node){
        Node<T> prev = null;
        if (node == null || node.next == null) {
            return node;
        } else {
            // 递归找到最后一个节点
            prev = recursionReverse(node.next);
            // 设置当前节点的下一个下一个节点为前一个节点
            node.next.next = node;
            // 设置当前节点的下一个节点为null
            node.next = null;
        }
        return prev;
    }

### 遍历显示链表数据 ###

实现思路：

1.  判断链表是否为空
2.  定义一个临时变量，用于遍历的时候，节点向后移动
3.  遍历整个链表，依次打印输出

public void showLinkedList(Node<T> node){
        if (node == null || node.next == null) {
            System.out.println("linkedList is empty");
            return;
        }
    
        Node<T> tempNode = node; // 将头节点赋值给临时节点
        while (true){
            System.out.println(tempNode); // 输出节点信息
            if(tempNode.next == null){ // 判断是不是最后一个节点
                break;
            }
            tempNode = tempNode.next; // 节点向后移动
        }
    }

### 完整示例代码 ###

public class SingleLinkedList<T> {
    
        private Node<T> head = new Node<>(); // 头节点
    
        /**
         * 判断链表是否为空
         *
         * @return
         */
        public boolean isEmpty(){
            return head == null || head.next == null;
        }
    
        /**
         * 添加节点到单向链表
         *
         * @param item
         * @return
         */
        public boolean add(T item){
            Node<T> newNode = new Node<>(item);
    
            Node<T> tempNode = head; // 将头节点赋值给临时节点
            while(tempNode.next != null){ // 遍历找到最后一个节点
                tempNode = tempNode.next;
            }
    
            tempNode.next = newNode; // 将最后一个节点的next指向新的节点
            return true;
        }
    
        /**
         * 修改节点数据
         *
         * @param sourceItem 节点原数据
         * @param tragetItem 节点新数据
         * @return
         */
        public boolean update(T sourceItem, T tragetItem) {
            if (this.isEmpty()) {
                System.out.println("linkedList is empty");
                return false;
            }
    
            Node<T> tempNode = head; // 将第一个节点赋值给临时节点
            while (true) {
                if (tempNode == null) {
                    System.out.println("node is empty");
                    break;
                }
                if (sourceItem.equals(tempNode.item)) {
                    tempNode.item = tragetItem;
                    return true;
                }
                tempNode = tempNode.next;
            }
    
            return false;
        }
    
        /**
         * 删除节点
         *
         * @param item 节点数据
         * @return
         */
        public boolean remove(T item) {
            if (this.isEmpty()) {
                System.out.println("linkedList is empty");
                return false;
            }
    
            Node<T> tempNode = head; // 将头节点赋值给临时节点
            while (true) {
                if (tempNode.next == null) {
                    System.out.println("node next is empty");
                    break;
                }
                if (item.equals(tempNode.next.item)) {
                    tempNode.next = tempNode.next.next;
                    return true;
                }
                tempNode = tempNode.next;
            }
            System.out.println("not find node item");
            return false;
        }
    
        /**
         * 获取队列长度
         *
         * @return
         */
        public int size() {
            if (this.isEmpty()) {
                return 0;
            }
    
            int size = 0;
            Node<T> tempNode = head; // 将头节点赋值给临时节点
            while (tempNode.next != null) { // 遍历找到最后一个节点
                size++;
                tempNode = tempNode.next;
            }
    
            return size;
        }
    
        /**
         * 查找（查找单链表中的倒数第k个结点）
         *
         * @param index
         * @return
         */
        public Node<T> findLastIndexNode(int index){
            if(this.isEmpty()){
                return null;
            }
    
            int size = this.size(); // 获取链表长度
            if(index <= 0 || index > size){
                return null;
            }
    
            Node<T> tempNode = head.next; // 将第一个有效节点赋值给临时变量
            for (int i = 0; i < size - index; i++) {
                tempNode = tempNode.next;
            }
    
            return tempNode;
        }
    
        /**
         * 非递归反转链表：从头部开始处理，依次替换位置
         *
         * @return
         */
        public Node<T> reverseLinkList() {
            // 如果当前链表为空或者只有一个节点，则无需反转，直接返回
            if (this.isEmpty() || head.next.next == null) {
                return head;
            }
    
            Node<T> tempNode = head.next; // 将第一个有效节点赋值给临时变量
            Node<T> prev = null; // 临时变量前一个节点
            while (tempNode != null) {
                Node<T> next = tempNode.next; // 当前节点的下一个节点
                Node<T> currentNode = tempNode; // 当前遍历的节点
                // 将前一个节点赋值给当前节点的下一个节点(此处是进行节点反转)
                // 比如有a、b、c、d、e等5个几点，那第一个节点为a
                // 进行反转的话，a就成了最后一个节点，所以a的next = prev（当遍历第一个节点的时候，prev就等于null）
                // 遍历第二个节点b的时候，b的next就是prev，前一个节点为a，所以b就到了a的前面
                // 后面依次遍历
                currentNode.next = prev;
                // 将当前节点赋值给临时变量 -> 前一个节点
                prev = currentNode;
                tempNode = next; // 往后移动一个节点（a -> b）
            }
            return prev;
        }
    
        /**
         * 递归反转node节点：从尾部开始处理
         *
         * @return
         */
        public Node<T> recursionReverseLinkList() {
            // 如果当前链表为空或者只有一个节点，则无需反转，直接返回
            if (this.isEmpty() || head.next.next == null) {
                return head;
            }
            return recursionReverse(head);
        }
    
        /**
         * 递归反转
         *
         * @param node
         * @return
         */
        public Node<T> recursionReverse(Node<T> node){
            Node<T> prev = null;
            if (node == null || node.next == null) {
                return node;
            } else {
                // 递归找到最后一个节点
                prev = recursionReverse(node.next);
                // 设置当前节点的下一个下一个节点为前一个节点
                node.next.next = node;
                // 设置当前节点的下一个节点为null
                node.next = null;
            }
            return prev;
        }
    
        /**
         * 显示链表数据
         *
         */
        public void showLinkedList(){
            if (this.isEmpty()) {
                System.out.println("linkedList is empty");
                return;
            }
    
            Node<T> tempNode = head; // 将头节点赋值给临时节点
            while (true){
                System.out.println(tempNode); // 输出节点信息
                if(tempNode.next == null){ // 判断是不是最后一个节点
                    break;
                }
                tempNode = tempNode.next; // 节点向后移动
            }
        }
    
        /**
         * 根据指定节点显示链表数据
         *
         * @param node
         */
        public void showLinkedList(Node<T> node){
            if (node == null || node.next == null) {
                System.out.println("linkedList is empty");
                return;
            }
    
            Node<T> tempNode = node; // 将头节点赋值给临时节点
            while (true){
                System.out.println(tempNode); // 输出节点信息
                if(tempNode.next == null){ // 判断是不是最后一个节点
                    break;
                }
                tempNode = tempNode.next; // 节点向后移动
            }
        }
    
        /**
         * 链表节点类
         *
         * @param <T>
         */
        private class Node<T>{
            private T item; // 节点数据
            private Node<T> next; // 下一个节点
    
            public Node(){
            }
    
            public Node(T item){
                this.item = item;
            }
    
            public Node(T item,Node<T> next){
                this.item = item;
                this.next = next;
            }
    
            @Override
            public String toString() {
                return "Node{" + "item=" + item + '}';
            }
        }
    }

public class SingleLikedListTest {
        public static void main(String[] args) {
    
            SingleLinkedList singleLikedList = new SingleLinkedList<String>();
            singleLikedList.add("a");
            singleLikedList.add("b");
            singleLikedList.add("c");
            singleLikedList.add("d");
            singleLikedList.add("e");
            System.out.println("删除前：");
            singleLikedList.showLinkedList();
    
            singleLikedList.remove("b");
            System.out.println("删除d后：");
            singleLikedList.showLinkedList();
    
            singleLikedList.update("e","f");
            System.out.println("将e修改为f后：");
            singleLikedList.showLinkedList();
    
            System.out.println("链表节点个数：" + singleLikedList.size());
    
            System.out.println("查找链表种倒数第1个节点："+ singleLikedList.findLastIndexNode(1));
    
            System.out.println("非递归反转链表：");
    //        singleLikedList.showLinkedList(singleLikedList.reverseLinkList());
    
            System.out.println("递归反转链表：");
            singleLikedList.showLinkedList(singleLikedList.recursionReverseLinkList());
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70]: /images/20211229/94a62712cb0843f0be88457c51d9d738.png
[20190623182710543.png]: /images/20211229/e2a5a47641c8445e8b068037549195da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20211229/642f0c8adb224ebeabd7a50015f214d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20211229/845dd4245cc949478eb672502ff8b79f.png