单向链表是一种线性表，由一些节点（Node）组成。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

单链表的实现

public class MyLinkList {
    Node head = null; // 头节点

    /**
     * 链表中的节点，data代表节点的值，next是指向下一个节点的引用
     */
    class Node {
        // 本节点的内容
        int data;
        // 下一个节点的引用
        Node next = null;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 向链表中插入数据
     *
     * @param data
     */
    public void addNode(int data) {
        // 实例化一个节点
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node temp = head;
        // 从头节点开始遍历单链表，直到遍历到最后一个则跳出循环
        while (temp.next != null) {
            //指向下一个节点
            temp = temp.next;
        }
        //temp是最后一个节点，将新增的节点放到temp后
        temp.next = newNode;
    }

    /**
     * 计算单链表的长度，也就是有多少个结点
     *
     * @return 结点个数
     */
    public int length() {
        int length = 0;
        Node temp = head;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    /**
     * 遍历单链表，打印所有节点的数据
     */
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node current = this.head;
        while(current != null){
            sb.append(current.data+"->");
            current = current.next;
        }
        return sb.toString();
    }
    
}

操作链表

链表反转

/**
 * 链表反转
 * @param head 头结点
 * @return
 */
public Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node temp = null;
    //创建虚拟头节点
    Node prev = null;
    Node current = head;
    while (current != null) {
        //保存下一个节点
        temp = current.next;
        //将当前节点的 next 指针改为指向前一个节点
        current.next = prev;
        //前一节点改成当前节点
        prev = current;
        //当前节点变成了下一节点
        current = temp;
    }
    this.head = prev;
    return prev;
}

查找单链表的中间节点：快慢指针法

/**
 * 查找单链表的中间节点：快慢指针法
 * 采用快慢指针的方式查找单链表的中间节点，快指针一次走两步，慢指针一次走一步，当快指针走完时，慢指针刚好到达中间节点
 *
 * @param head
 * @return
 */
public Node searchMid(Node head) {
    Node slow = this.head;
    Node fast = this.head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    System.out.println("链表中间节点是:" + slow.data);
    return fast;
}

查找单链表的中间节点：数组法

/**
 * 查找单链表的中间节点：数组法
 * @return
 */
public Node searchMid2(){
    Node[] arr = new Node[this.length() + 1];
    int t = 0;
    Node temp = head;
    while(temp != null){
        arr[t++] = temp;
        temp = temp.next;
    }
    return arr[t/2];
}

在链表的指定位置插入节点

/**
 * insertNodeByIndex:在链表的指定位置插入结点。
 * 插入操作需要知道1个结点即可，当前位置的前一个结点
 * index:插入链表的位置，从1开始
 * node:插入的结点
 */
public void insertNodeByIndex(int index, Node node) {
    //首先需要判断指定位置是否合法，
    if (index < 1 || index > length() + 1) {
        System.out.println("插入位置不合法。");
        return;
    }
    //记录我们遍历到第几个结点了，也就是记录位置。
    int length = 1;
    //可移动的指针
    Node temp = head;
    //遍历单链表
    while (head.next != null) {
        //判断是否到达指定位置。
        if (index == length++) {
            //注意，我们的temp代表的是当前位置的前一个结点。
            //前一个结点        当前位置        后一个结点
            //temp            temp.next     temp.next.next
            //插入操作。
            node.next = temp.next;
            temp.next = node;
            return;
        }
        temp = temp.next;
    }
}

删除第index个节点

/**
 * 删除第index个节点
 */
public boolean delNodeByIndex(int index) {
    if (index < 1 || index > length()) {
        return false;
    }
    if (index == 1) {
        head = head.next;
        return true;
    }

    int length = 1;
    Node temp = head;
    while (temp.next != null) {
        if (index == length++) {
            //删除操作。
            temp.next = temp.next.next;
            return true;
        }
        temp = temp.next;
    }
    return false;
}

在不知道头指针的情况下删除指定节点

/**
 * 在不知道头指针的情况下删除指定节点
 */
public boolean deleteNode11(Node n) {
    if (n == null || n.next == null) {
        return false;
    }
    int tmp = n.data;
    n.data = n.next.data;
    n.next.data = tmp;
    n.next = n.next.next;
    System.out.println("删除成功！");
    return true;
}

查找倒数第K个元素

/**
* 查找倒数 第k个元素
* 采用两个指针P1,P2，P1先前移K步，然后P1、P2同时移动，当p1移动到尾部时，P2所指位置的元素即倒数第k个元素
*
* @param head
* @param k
* @return
*/
public Node findElem(Node head, int k) {
    if (k < 1 || k > this.length()) {
        return null;
    }
    Node p1 = head;
    Node p2 = head;
    for (int i = 0; i < k; i++)// 前移k步
        p1 = p1.next;
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

对链表进行排序

/**
 * 对链表进行排序
 */
public Node orderList() {
    Node nextNode = null;
    int tmp = 0;
    Node curNode = head;
    while (curNode.next != null) {
        nextNode = curNode.next;
        while (nextNode != null) {
            if (curNode.data > nextNode.data) {
                tmp = curNode.data;
                curNode.data = nextNode.data;
                nextNode.data = tmp;
            }
            nextNode = nextNode.next;
        }
        curNode = curNode.next;
    }
    return head;
}

删除链表中的重复节点

/**
 * 删除链表中的重复节点
 */
public static void deleteDuplicate(Node head) {
    Node p = head;
    while (p != null) {
        Node q = p;
        while (q.next != null) {
            if (p.data == q.next.data) {
                q.next = q.next.next;
            } else
                q = q.next;
        }
        p = p.next;
    }

}

从尾到头输出节点

/**
 * 从尾到头输出单链表，采用递归方式实现
 */
public void printListReversely(Node node) {
    if (node != null) {
        printListReversely(node.next);
        System.out.println("printListReversely:" + node.data);
    }
}

public static void main(String[] args) {
    MyLinkList list = new MyLinkList();
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.addNode(4);
    list.addNode(5);

    list.printListReversely(list.head);
}

双向链表的实现

双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

package com.wjy.test;

/**
 * @author: wjy
 * @Date: Create in 21:25 2021/11/16
 * @description : Java 实现的双向链表。
 * JDK自带的双向链表：java.util.LinkedList
 */
public class DoubleLink<T> {

    // 表头
    private DNode<T> mHead;
    // 节点个数
    private int mCount;

    // 双向链表“节点”对应的结构体
    private class DNode<T> {
        public DNode prev;
        public DNode next;
        public T value;

        public DNode(T value, DNode prev, DNode next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

    // 构造函数
    public DoubleLink() {
        // 创建“表头”。注意：表头没有存储数据！
        mHead = new DNode<T>(null, null, null);
        mHead.prev = mHead.next = mHead;
        // 初始化“节点个数”为0
        mCount = 0;
    }

    // 返回节点数目
    public int size() {
        return mCount;
    }

    // 返回链表是否为空
    public boolean isEmpty() {
        return mCount==0;
    }

    // 获取第index位置的节点
    private DNode<T> getNode(int index) {
        if (index<0 || index>=mCount)
            throw new IndexOutOfBoundsException();

        // 正向查找
        if (index <= mCount/2) {
            DNode<T> node = mHead.next;
            for (int i=0; i<index; i++)
                node = node.next;

            return node;
        }

        // 反向查找
        DNode<T> rnode = mHead.prev;
        int rindex = mCount - index -1;
        for (int j=0; j<rindex; j++)
            rnode = rnode.prev;

        return rnode;
    }

    // 获取第index位置的节点的值
    public T get(int index) {
        return getNode(index).value;
    }

    // 获取第1个节点的值
    public T getFirst() {
        return getNode(0).value;
    }

    // 获取最后一个节点的值
    public T getLast() {
        return getNode(mCount-1).value;
    }

    // 将节点插入到第index位置之前
    public void insert(int index, T t) {
        if (index==0) {
            DNode<T> node = new DNode<T>(t, mHead, mHead.next);
            mHead.next.prev = node;
            mHead.next = node;
            mCount++;
            return ;
        }

        DNode<T> inode = getNode(index);
        DNode<T> tnode = new DNode<T>(t, inode.prev, inode);
        inode.prev.next = tnode;
        inode.next = tnode;
        mCount++;
        return ;
    }

    // 将节点插入第一个节点处。
    public void insertFirst(T t) {
        insert(0, t);
    }

    // 将节点追加到链表的末尾
    public void appendLast(T t) {
        DNode<T> node = new DNode<T>(t, mHead.prev, mHead);
        mHead.prev.next = node;
        mHead.prev = node;
        mCount++;
    }

    // 删除index位置的节点
    public void del(int index) {
        DNode<T> inode = getNode(index);
        inode.prev.next = inode.next;
        inode.next.prev = inode.prev;
        inode = null;
        mCount--;
    }

    // 删除第一个节点
    public void deleteFirst() {
        del(0);
    }

    // 删除最后一个节点
    public void deleteLast() {
        del(mCount-1);
    }
}

双链表测试

/**
 * Java 实现的双向链表。
 * 注：java自带的集合包中有实现双向链表，路径是:java.util.LinkedList
 *
 * @author skywang
 * @date 2013/11/07
 */
public class DlinkTest {

    // 双向链表操作int数据
    private static void int_test() {
        int[] iarr = {10, 20, 30, 40};

        System.out.println("\n----int_test----");
        // 创建双向链表
        DoubleLink<Integer> dlink = new DoubleLink<Integer>();

        dlink.insert(0, 20);    // 将 20 插入到第一个位置
        dlink.appendLast(10);    // 将 10 追加到链表末尾
        dlink.insertFirst(30);    // 将 30 插入到第一个位置

        // 双向链表是否为空
        System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
        // 双向链表的大小
        System.out.printf("size()=%d\n", dlink.size());

        // 打印出全部的节点
        for (int i=0; i<dlink.size(); i++)
            System.out.println("dlink("+i+")="+ dlink.get(i));
    }


    private static void string_test() {
        String[] sarr = {"ten", "twenty", "thirty", "forty"};

        System.out.println("\n----string_test----");
        // 创建双向链表
        DoubleLink<String> dlink = new DoubleLink<String>();

        dlink.insert(0, sarr[1]);    // 将 sarr中第2个元素 插入到第一个位置
        dlink.appendLast(sarr[0]);    // 将 sarr中第1个元素 追加到链表末尾
        dlink.insertFirst(sarr[2]);    // 将 sarr中第3个元素 插入到第一个位置

        // 双向链表是否为空
        System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
        // 双向链表的大小
        System.out.printf("size()=%d\n", dlink.size());

        // 打印出全部的节点
        for (int i=0; i<dlink.size(); i++)
            System.out.println("dlink("+i+")="+ dlink.get(i));
    }


    // 内部类
    private static class Student {
        private int id;
        private String name;

        public Student(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "["+id+", "+name+"]";
        }
    }

    private static Student[] students = new Student[]{
        new Student(10, "sky"),
        new Student(20, "jody"),
        new Student(30, "vic"),
        new Student(40, "dan"),
    };

    private static void object_test() {
        System.out.println("\n----object_test----");
        // 创建双向链表
        DoubleLink<Student> dlink = new DoubleLink<Student>();

        dlink.insert(0, students[1]);    // 将 students中第2个元素 插入到第一个位置
        dlink.appendLast(students[0]);    // 将 students中第1个元素 追加到链表末尾
        dlink.insertFirst(students[2]);    // 将 students中第3个元素 插入到第一个位置

        // 双向链表是否为空
        System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
        // 双向链表的大小
        System.out.printf("size()=%d\n", dlink.size());

        // 打印出全部的节点
        for (int i=0; i<dlink.size(); i++) {
            System.out.println("dlink("+i+")="+ dlink.get(i));
        }
    }


    public static void main(String[] args) {
        int_test();        // 演示向双向链表操作“int数据”。
        string_test();    // 演示向双向链表操作“字符串数据”。
        object_test();    // 演示向双向链表操作“对象”。
    }
}

单链表的实现#

操作链表#

链表反转#

查找单链表的中间节点：快慢指针法#

查找单链表的中间节点：数组法#

在链表的指定位置插入节点#

删除第index个节点#

在不知道头指针的情况下删除指定节点#

查找倒数第K个元素#

对链表进行排序#

删除链表中的重复节点#

从尾到头输出节点#

双向链表的实现#

双链表测试#