Java手写链表

- 简单介绍
- 头插法和尾插法
- 单向链表
- 双向链表
- 循环链表

简单介绍

链表是java数据结构中一种很基础很常见又很重要的数据结构，JDK中许多内置jar包基于单链表实现，比如像我们熟悉的linkedList。
链表的数据结构非常简单，就是一个个节点连接在一起，形成一个完整的链条，每个节点包含2部分，数据域date，和一个指向下一个节点引用的指针next（java中我们叫引用）
如图：

链表的分类有很多种，比如单向链表，双向链表，循环链表等

头插法和尾插法

在链表中插入操作还是比较重要的，因此我先用图示介绍一下这两种插入方式（以单向链表为例）

头插法

核心：

newNode.next = head.next;	// 新增节点的next域指向头节点的next节点	
head.next = newNode;		// 头结点的next域再指向新增节点

动画：

尾插法

尾插法：需要借助一个指针rear，指向当前链表最后一个节点，每次处理rear指针指向的节点和新增的节点的关系即可。

核心：

rear.next = newNode;    // 尾节点的next域指向新节点
rear = newNode;         // 尾指针变成newNode指针

动画：

单向链表

首先自定义一个单链表类

static class SinglelinkedList {
    public int size;        // 链表大小
    public Node head = new Node<>();    // 头结点 (先初始化一下)
    public Node rear = head;    // 尾节点 (刚开始指向头结点)
    
    private class Node {
        T date;         // date存储数据
        Node next;   // 存储下个节点的引用指针

        public Node(T date) {
            this.date = date;
            this.next = null;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "date=" + date +
                    '}';
        }
    }
}

注意：

首先定义SinglelinkedList类，这里接收的数据我们用一个泛型来规范。
再定义一个Node节点类，这个相当于一个容器。（如果把SinglelinkedList比喻成整个糖葫芦，那么Node就是糖葫芦上的山楂果）。Node节点需要有两个属性：date用来存储数据，next用来指向下个node节点。
因为是单向链表，因此头结点head是不可缺少的；因为我们是尾插法因此这里最好加一个尾指针rear；同时加个size来记录链表的长度。

添加方法（尾插法）

public void addRear(T date) {
    // 根据添加的内容 创建一个新节点  next域为null
    Node newNode = new Node<>(date);
    rear.next = newNode;    // 尾节点的next指向新节点
    rear = newNode;         // 将新节点设置为尾节点
    size++;                 // 链表大小 +1
}

添加方法（头插法）

public void addHead(T date) {
    // 根据添加的内容 创建一个新节点  next域为null
    Node newNode = new Node<>(date);
    newNode.next = head.next;	// 新增节点的next域指向头节点的next节点
    head.next = newNode;		// 头结点的next域再指向新增节点
    size++;
}

插入方法

public void insert(T date, int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return;
    }
    Node temp = head;
    for (int i=1; i<=index-1; i++) {    // 找到插入位置的前一个节点 因此是index-1 因为这是单向链表 不能指向前一个节点
        temp = temp.next;
    }
    // 根据添加的内容 创建一个新节点  next域为null
    Node newNode = new Node<>(date);
    // 关键逻辑
    newNode.next = temp.next;
    temp.next = newNode;
    size++;
}

删除方法

public void delete(int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return;
    }
    Node temp = head;
    for (int i=1; i<=index-1; i++) {  // 找到插入位置的前一个节点 因此是index-1 因为这是单向链表 不能指向前一个节点
        temp = temp.next;
    }
    // 主要逻辑
    temp.next = temp.next.next;
    if (index == size) {    // 如果删除的是最后一个节点
        rear = temp;        // 将倒数第二个节点设置为尾节点
    }
    size--;
}

修改方法

public void update(T date, int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return;
    }
    Node temp = head;
    for (int i=1; i<=index; i++) {  // 注意这里是 index不是index-1  和上面的插入方法是有区别的
        temp = temp.next;
    }
    // 找到指定节点后 直接修改它的date即可
    temp.date = date;
}

链表遍历方法

public void showList() {
    if (this.size == 0) {
        System.out.println("链表为空！");
        return;
    }
    Node temp = head;   // 因为head不能动 因此这里我们需要添加一个临时指针
    while (true) {
        if (temp == null) break;
        System.out.println(temp);
        temp = temp.next;   // 这点很重要 临时节点后移 （别错写成 temp.next = temp 了）
    }
}

获取指定下标的节点值方法

public Object get(int index) {
    if (index > size) {
        System.out.println("下标超出链表大小");
        return -1;
    }
    Node temp = head;
    for (int i=1; i<=index; i++) {
        temp = temp.next;
    }
    return temp.date;
}

测试

测试代码：

SinglelinkedList myList = new SinglelinkedList<>();
myList.addRear("字节跳动");myList.addRear("阿里");myList.addRear("腾讯");myList.addRear("美团");
myList.showList();
System.out.println("链表的大小："+myList.size);

myList.insert("华为",4);
myList.showList();
System.out.println("链表的大小："+myList.size);

myList.update("百度",5);
myList.showList();
System.out.println("链表的大小："+myList.size);

myList.delete(3);
myList.showList();
System.out.println("链表的大小："+myList.size);

System.out.println(myList.get(1));

myList.addHead("上官婉儿");
myList.addHead("橘右京");
myList.addHead("廉颇");
myList.showList();
System.out.println("链表的大小："+myList.size);

输出：

Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=美团}
链表的大小：4
Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=华为}
Node{date=美团}
链表的大小：5
Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=华为}
Node{date=百度}
链表的大小：5
Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=华为}
Node{date=百度}
链表的大小：4
字节跳动
Node{date=null}
Node{date=廉颇}
Node{date=橘右京}
Node{date=上官婉儿}
Node{date=字节跳动}
Node{date=阿里}
Node{date=华为}
Node{date=百度}
链表的大小：7

进阶—单链表的反转【腾讯面试题】

思路
其实很简单。首先创建一个新的链表，然后遍历之前老的链表，将一个个节点用头插法的方式添加到新的链表中，这里头插法很关键。

代码实现：

public void reverse() {
    // 首先创建一个新的临时链表
    SinglelinkedList templinkedList = new SinglelinkedList();
    // 开始遍历 从头结点的next节点开始
    Node curNode = this.head.next;
    while (true) {
        if (curNode == null) break;
        // 将当前节点利用 头插法 添加到临时链表中 （头插法是关键）
        templinkedList.addHead(curNode.date);
        curNode = curNode.next;
    }
    // 最后把临时链表的head索引赋值给当前链表的head
    this.head = templinkedList.head;
}

测试代码：

SinglelinkedList myList = new SinglelinkedList<>();
myList.addRear("字节跳动");myList.addRear("阿里");
myList.addRear("腾讯");myList.addRear("美团");
myList.addRear("华为");
myList.showList();
myList.reverse();
System.out.println("--------------反转后------------");
myList.showList();

输出结果：

Node{date=null}
Node{date=字节跳动}
Node{date=阿里}
Node{date=腾讯}
Node{date=美团}
Node{date=华为}
--------------反转后------------
Node{date=null}
Node{date=华为}
Node{date=美团}
Node{date=腾讯}
Node{date=阿里}
Node{date=字节跳动}

双向链表

自定义双向链表类

其实和单向链表大同小异，区别在于双向链表的Node节点有两个指针，一个指向下一个节点-next，一个指向上一个节点-pre。
其他的增加、删除方法要注意处理next、pre的指向关系

代码实现：

static class DoublelinkedList {
    public int size;        // 链表大小
    public Node head = new Node();    // 头结点 (先初始化一下)
    public Node rear = head;    // 尾节点 (刚开始指向头结点)

    
    public void addRear(T date) {
        // 根据添加的内容 创建一个新节点  next域为null
        Node newNode = new Node(date);
        rear.next = newNode;    // 尾节点的next域指向新节点
        newNode.pre = rear;     // 新节点的pre域执行尾节点
        rear = newNode;         // 将新添加的节点设置为尾节点
        size++;                 // 链表大小 +1
    }

    
    public void addHead(T date) {
        // 根据添加的内容 创建一个新节点  next域为null
        Node newNode = new Node(date);
        // 主要逻辑
        newNode.next = head.next;
        head.next.pre = newNode;
        head.next = newNode;
        newNode.pre = head;
        size++;
    }


    
    public void delete(int index) {
        if (index > size) {
            System.out.println("下标超出链表大小");
            return;
        }
        Node temp = head;
        for (int i=1; i<=index; i++) {  // 找到对应下标的节点
            temp = temp.next;
        }
        // 主要逻辑
        if (index < size) { // 要删除的节点不是最后一个节点
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
        }else { // 要删除的节点是最后一个节点
            rear = temp.pre;        // 将倒数第二个节点设置为尾节点
            temp.pre.next = null;  // 然后将倒数第二个节点的next指向为null即可

        }
        size--;
    }

	
    public void update(T date, int index) {
        if (index > size) {
            System.out.println("下标超出链表大小");
            return;
        }
        Node temp = head;
        for (int i=1; i<=index; i++) {
            temp = temp.next;
        }
        // 找到指定节点后 直接修改它的date即可
        temp.date = date;
    }

    
    public void showList() {
        if (this.size == 0) {
            System.out.println("链表为空！");
            return;
        }
        Node temp = head;   // 因为head不能动 因此这里我们需要添加一个临时指针
        while (true) {
            if (temp == null) break;
            System.out.println(temp);
            temp = temp.next;   // 这点很重要 临时节点后移 （别错写成 temp.next = temp 了）
        }
    }


    
    private class Node {
        T date;         // date存储数据
        Node next;   // 指向下一个节点
        Node pre;    // 指向上一个节点

        public Node(T date) {
            this.date = date;
            this.next = null;
            this.pre = null;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "date=" + date +
                    '}';
        }
    }
}

测试代码：

DoublelinkedList

Java手写链表

Java相关栏目本月热门文章