1、链表基本介绍

链表是有序的列表,在内存中的存储如下:
 
1、链表是以结点的方式来存储,是链式存储;
2、每个结点都包含data域、next域;
3、链表的每个结点在存储上不一定连续;
4、链表分带头结点和不带头结点的链表,根据实际需求而定;
带头结点的链表示意图:
 

2、单向链表

单向链表指的是只有一个方向。
 

2.1 单向链表的结点类

package cn.klb.datastructures.linkedlist;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 单向链表结点类
 * @Date: Create in 2023/3/31 12:51
 * @Modified By:
 */
public class SinglyNode {
   
     
    public int no;  // 编号
    public String data; // 字符串数据
    public SinglyNode next;   // 指向下一个结点

    /**
     * 构造方法,不带next
     *
     * @param no
     * @param data
     */
    public SinglyNode(int no, String data) {
   
     
        this.no = no;
        this.data = data;
    }

    @Override
    public String toString() {
   
     
        return "Node{" +
                "no=" + no +
                ", data='" + data + '\'' +
                '}';
    }
}

2.2 单向链表类

package cn.klb.datastructures.linkedlist;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description:
 * @Date: Create in 2023/3/30 20:13
 * @Modified By:
 */
public class SinglyLinkedList {
   
     
    private SinglyNode head = new SinglyNode(0, ""); // 定义头结点

    public SinglyNode getHead() {
   
     
        return head;
    }

    /**
     * 添加结点
     * 模式:不考虑编号顺序,直接添加到链表末尾
     * 思路:找到链表的末尾结点,末尾结点的next指向新结点
     *
     * @param SinglyNode
     */
    public void add(SinglyNode SinglyNode) {
   
     
        SinglyNode temp = head;   // temp理解为一个结点索引

        // 从head开始,遍历链表,找到next为null的就是最后一个结点
        while (true) {
   
     
            if (temp.next == null) {
   
     
                break;
            } else {
   
     
                temp = temp.next;
            }
        }

        // 跳出while循环,表明当前temp就是最后一个结点
        temp.next = SinglyNode;
    }

    /**
     * 添加结点
     * 模式:考虑编号顺序,整体链表的元素的编号从小到大排列
     * 思路:找到链表的末尾结点,末尾结点的next指向新结点
     *
     * @param SinglyNode
     */
    public void addByNo(SinglyNode SinglyNode) {
   
     
        SinglyNode temp = head;   // temp理解为一个结点索引
        boolean existFlag = false;  // 编号已存在,则不能插入

        // 从head开始,遍历链表
        while (true) {
   
     
            // 如果temp已经是最后一个结点,则直接插入
            if (temp.next == null) {
   
     
                break;
            }
            // 如果下一个结点的编号大于要插入的结点编号,则可以插入
            if (temp.next.no > SinglyNode.no) {
   
     
                break;
            }
            // 如果找到相等编号,则不能插入
            if (temp.next.no == SinglyNode.no) {
   
     
                existFlag = true;
                break;
            }
            temp = temp.next;
        }

        if (existFlag) {
   
     
            System.out.println("编号已存在,插入失败!");
        } else {
   
     
            SinglyNode.next = temp.next;
            temp.next = SinglyNode;
        }
    }

    /**
     * 修改结点
     * 覆盖编号相同的结点的data
     *
     * @param SinglyNode
     */
    public void update(SinglyNode SinglyNode) {
   
     
        // 判断链表是否为空
        if (head.next == null) {
   
     
            System.out.println("链表是空的,没的修改了。");
        } else {
   
     
            SinglyNode temp = head;
            // 找到和相同编号的结点
            while (true) {
   
     
                // 找到相同编号结点
                if (temp.next.no == SinglyNode.no) {
   
     
                    temp.next.data = SinglyNode.data;
                    break;
                }
                // 遍历到最后一个还是找不到相同编号的结点,则修改失败
                if (temp.next == null) {
   
     
                    System.out.println("找不到编号为" + SinglyNode.no + "结点,修改失败!");
                    break;
                }
                temp = temp.next;
            }
        }
    }

    /**
     * 根据编号删除对应结点
     *
     * @param no
     */
    public void delete(int no) {
   
     
        SinglyNode temp = head;
        while (true) {
   
     
            if (temp.next == null) {
   
     
                System.out.println("找不到编号为" + no + "结点,删除失败!");
                break;
            }
            if (temp.next.no == no) {
   
     
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 遍历显示链表
     */
    public void show() {
   
     
        SinglyNode temp = head;
        if (temp.next == null) {
   
     
            System.out.println("空链表,有什么好显示的。");
            return;
        }
        while (true) {
   
     
            if (temp == null) {
   
     
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 获取链表结点个数
     *
     * @return
     */
    public int size() {
   
     
        int size = 0;
        SinglyNode temp = head.next;
        while (temp != null) {
   
     
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 链表反转
     */
    public void reverse() {
   
     
        SinglyNode reverseHead = new SinglyNode(0, "");  // 反转后的头结点
        SinglyNode cur = head.next; // 当前结点
        SinglyNode next = null; // 当前结点的后结点

        while (cur != null) {
   
     
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }

        head.next = reverseHead.next;
    }

    /**
     * 查找倒数第 index 个结点
     * 思路:找倒数第 index 个,即找第 size-index 个
     *
     * @param index
     * @return
     */
    public SinglyNode findLastIndexNode(int index) {
   
     
        int size = this.size();

        // 有效值判断
        if (index < 0 || index > size) {
   
     
            return null;
        }

        SinglyNode temp = head.next;
        for (int i = 0; i < (size - index); i++) {
   
     
            temp = temp.next;
        }

        return temp;
    }

}

2.3 测试类

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.linkedlist.SinglyLinkedList;
import cn.klb.datastructures.linkedlist.SinglyNode;
import org.junit.Test;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description:
 * @Date: Create in 2023/3/31 12:49
 * @Modified By:
 */
public class SinglyLinkedListTest {
   
     

    /**
     * 测试增删改
     */
    @Test
    public void singlyLinkedListTest() {
   
     
        System.out.println("------list1------");
        SinglyLinkedList list1 = new SinglyLinkedList();
        list1.add(new SinglyNode(4, "周杰伦"));
        list1.add(new SinglyNode(7, "林俊杰"));
        list1.add(new SinglyNode(17, "张杰"));
        list1.show();

        System.out.println("------list2------");
        SinglyLinkedList list2 = new SinglyLinkedList();
        list2.add(new SinglyNode(4, "周杰伦"));
        list2.add(new SinglyNode(17, "张杰"));
        list2.add(new SinglyNode(7, "林俊杰"));
        list2.show();

        System.out.println("------list1 delete no:3 17------");
        list1.delete(3);
        list1.delete(17);
        list1.show();

        System.out.println("------list2 update {no=4,data=青花瓷}------");
        SinglyNode SinglyNode4 = new SinglyNode(4, "青花瓷");
        list2.update(SinglyNode4);
        list2.show();
    }

    @Test
    public void testSize() {
   
     
        SinglyLinkedList list = new SinglyLinkedList();
        list.add(new SinglyNode(4, "周杰伦"));
        list.add(new SinglyNode(7, "林俊杰"));
        list.add(new SinglyNode(17, "张杰"));
        System.out.println("节点个数为:" + list.size());
    }

    @Test
    public void testReverse() {
   
     
        SinglyLinkedList list = new SinglyLinkedList();
        list.add(new SinglyNode(4, "周杰伦"));
        list.add(new SinglyNode(7, "林俊杰"));
        list.add(new SinglyNode(17, "张杰"));
        list.show();
        System.out.println("-----链表反转------");
        list.reverse();
        list.show();
    }

    @Test
    public void testfindLastIndexNode() {
   
     
        SinglyLinkedList list = new SinglyLinkedList();
        list.add(new SinglyNode(4, "周杰伦"));
        list.add(new SinglyNode(7, "林俊杰"));
        list.add(new SinglyNode(12, "张杰"));
        list.add(new SinglyNode(1, "石鸣鸣"));
        list.add(new SinglyNode(24, "周星驰"));
        list.show();
        System.out.println("倒数第2个元素为:" + list.findLastIndexNode(2));
    }
}

3、双向链表

双向链表指的是每个结点都指向前和后,有两个方向。
 

3.1 双向链表的结点类

package cn.klb.datastructures.linkedlist;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description:
 * @Date: Create in 2023/3/31 17:32
 * @Modified By:
 */
public class DoubleLinkedNode {
   
     
    public int no;
    public String data;
    public DoubleLinkedNode pre;
    public DoubleLinkedNode next;

    public DoubleLinkedNode(int no,String data){
   
     
        this.no = no;
        this.data = data;
    }

    @Override
    public String toString() {
   
     
        return "DoubleLinkedNode{" +
                "no=" + no +
                ", data='" + data + '\'' +
                '}';
    }
}

3.2 双向链表类

package cn.klb.datastructures.linkedlist;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description:
 * @Date: Create in 2023/3/31 17:32
 * @Modified By:
 */
public class DoubleLinkedList {
   
     
    private DoubleLinkedNode head = new DoubleLinkedNode(0, "");    // 定义头结点

    /**
     * 显示双向链表
     */
    public void show() {
   
     
        if (head.next == null) {
   
     
            System.out.println("链表为空!");
        }

        // temp结点用于遍历
        DoubleLinkedNode temp = head.next;
        while (true) {
   
     
            if (temp == null) break;

            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 添加结点到尾端
     *
     * @param node
     */
    public void add(DoubleLinkedNode node) {
   
     
        DoubleLinkedNode temp = head;

        // 找到最后一个结点
        while (true) {
   
     
            if (temp.next == null) break;
            temp = temp.next;
        }

        temp.next = node;
        node.pre = temp;
    }

    /**
     * 根据结点编号来更新结点数据
     *
     * @param node
     */
    public void update(DoubleLinkedNode node) {
   
     
        // 如果链表没有结点,则直接返回
        if (head.next == null) return;

        // 定义临时节点来遍历找到和node相同no的结点
        DoubleLinkedNode temp = head.next;

        while (true) {
   
     
            if (temp.no == node.no) {
   
     
                temp.data = node.data;  // 更新data
                break;  //更新完即退出循环
            }
            if (temp == null) {
   
     
                System.out.println("要更新的结点不存在!");
                break;// 找不到相同no,直接退出
            }
            temp = temp.next;
        }
    }

    /**
     * 删除指定no的结点
     *
     * @param no
     */
    public void delete(int no) {
   
     
        DoubleLinkedNode temp = head.next;
        if (temp == null) {
   
     
            System.out.println("链表为空,删除失败!");
        }
        while (true) {
   
     
            if (temp == null) {
   
     
                System.out.println("找不到要删除的结点,删除失败!");
            }
            if (temp.no == no){
   
     
                temp.pre.next = temp.next;
                // 要删除的结点不是最后一个结点
                if(temp.next != null){
   
     
                    temp.next.pre = temp.pre;
                }
                break;  //删除完就结束循环
            }
            temp = temp.next;
        }
    }
}

3.3 测试类

package cn.klb.test.datastructurestest;

import cn.klb.DataStructures.LinkedList.DoubleLinkedList;
import cn.klb.DataStructures.LinkedList.DoubleLinkedNode;
import org.junit.Test;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description:
 * @Date: Create in 2023/3/31 17:34
 * @Modified By:
 */
public class DoubleLinkedListTest {
   
     

    @Test
    public void testAdd(){
   
     
        DoubleLinkedList list = new DoubleLinkedList();
        list.add(new DoubleLinkedNode(1,"石鸣鸣"));
        list.add(new DoubleLinkedNode(2,"周杰伦"));
        list.add(new DoubleLinkedNode(3,"蔡依林"));
        list.add(new DoubleLinkedNode(4,"蔡徐坤"));

        list.show();
    }

    @Test
    public void testUpdate(){
   
     
        DoubleLinkedList list = new DoubleLinkedList();
        list.add(new DoubleLinkedNode(1,"石鸣鸣"));
        list.add(new DoubleLinkedNode(2,"周杰伦"));
        list.add(new DoubleLinkedNode(3,"蔡依林"));
        list.add(new DoubleLinkedNode(4,"蔡徐坤"));
        System.out.println("-----修改前-----");
        list.show();

        DoubleLinkedNode node = new DoubleLinkedNode(1,"大帅哥");
        System.out.println("-----修改后-----");
        list.update(node);
        list.show();
    }

    @Test
    public void testDelete(){
   
     
        DoubleLinkedList list = new DoubleLinkedList();
        list.add(new DoubleLinkedNode(1,"石鸣鸣"));
        list.add(new DoubleLinkedNode(2,"周杰伦"));
        list.add(new DoubleLinkedNode(3,"蔡依林"));
        list.add(new DoubleLinkedNode(4,"蔡徐坤"));
        System.out.println("-----修改前-----");
        list.show();

        list.delete(2);
        System.out.println("-----修改后-----");
        list.show();
    }
}