数据结构——链表的实现（Java版）

目录

一、链表

二、代码实现

1.创建结点

2.构造函数

3.链表的相关属性

4.添加虚拟节点

5.判断链表是否为空

6.添加方法

（1）在头部添加

（2）在尾部添加

（3）在索引位置添加

（4）对头插法和尾插法代码进行简化（调用任意位置添加的方法）

7.打印链表（遍历，重写toString方法）

8.获取链表元素个数（链表长度）

9.获取链表结点

（1）获取头结点

（2）获取尾结点

（3）获取指定位置结点

10.判断结点是否存在

11.删除结点

（1）删除头结点

（2）删除尾节点

（3）在指定位置删除结点

（4）删除元素

（5）不使用虚拟节点删除

一、链表

链表是真正的动态数据结构，也是最简单的动态数据结构。

动态数据结构还有：二叉树，trie等

优点：不需要处理固定容量的问题，真正的动态

缺点：丧失了随机访问的能力

学习链表有助于更深理解引用和递归

二、代码实现

1.创建结点

使用内部类来创建结点

//使用内部类——创建结点
    class Node<T>{
        T data;//节点本身
        Node next;//指向下个节点

2.构造函数

两个构造函数（传入的参数不同）

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

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

    }

3.链表的相关属性

头结点和结点个数（链表长度）

private Node head;//头结点
    private int size;//表示链表中有多少个结点

4.添加虚拟节点

public SelfLinkedList(){
        //创建一个虚拟头结点
        Node dummyHead=new Node(Integer.MIN_VALUE);
        this.head=dummyHead;
        this.size=0;

        dummyHead.next=head;
    }

5.判断链表是否为空

public boolean isEmpty(){
        return this.size==0;
    }

6.添加方法

（1）在头部添加

public void addHead(T data){
        //创建一个节点
        Node node= new Node(data);
        //挂接
        node.next=this.head;
        this.head=node;
        //更新size
        this.size++;
    }

（2）在尾部添加

public void addTail(T data){
        Node node=new Node(data);
        //针对空链表做处理
        if(this.head==null){
            this.head=node;
            this.size++;
            return;
        }
        Node curNode=this.head;
        while(curNode.next!=null){
            curNode=curNode.next;
        }
        curNode.next=node;
        this.size++;
    }

（3）在索引位置添加

//在任意位置添加
    public void add(int index,T data){
        //判断index是否有效
        if(index<0||index>this.size){
            throw new IllegalArgumentException("index is invalid");
        }
        //创建一个节点
        Node node= new Node(data);
        //特殊处理1：如果索引为0,
        if(index==0){
            this.head=new Node(data,this.head);
            this.size++;
            return;
        }
        //特殊处理2：链表为空（异常已抛出）
        //找前驱结点，从头开始找，让索引移动index-1次
        Node pre=this.head;
        for(int i=1;i<=index;i++){
            pre=pre.next;
        }
        //开始进行结点的挂接
        node.next=pre.next;
        pre.next=node;
        this.size++;
    }

（4）对头插法和尾插法代码进行简化（调用任意位置添加的方法）

//在头部添加
    public void addHead(T data){
       
        add(0,data);
    }

    //在尾部添加
    public void addTail(T data){
        
        add(this.size,data);
    }

7.打印链表（遍历，重写toString方法）

//打印整个链表
    @Override
    public String toString() {
        //从this。head开始一直向后
        Node curNode=this.head.next;
        StringBuilder sb=new StringBuilder();
        while(curNode!=null){
            sb.append(curNode.data+"-->");
            curNode=curNode.next;
        }
        sb.append("null");
        return sb.toString();
    }

8.获取链表元素个数（链表长度）

 //获取链表中元素的个数
    public int getSize(){
        return this.size;
    }

9.获取链表结点

（1）获取头结点

//获取链表的头结点
    public Optional getFirst(){
        if(this.head.next==null){
            return Optional.empty();
        }
        return Optional.ofNullable(this.head.next.data);
    }

（2）获取尾结点

//获取链表的尾结点
    public Optional getLast(){
        if(this.head.next==null){
            return Optional.empty();
        }
        Node<T> curNode=this.head;
        while(curNode.next!=null){
            curNode=curNode.next;
        }
        return Optional.of(curNode.data);
    }

（3）获取指定位置结点

 //从链表中获取任意位置的结点
    public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("index is invalid");
        }
        Node<T> curNode = this.head.next;
        int i = 0;
        while (i < index) {
            curNode = curNode.next;
            i++;
        }
        return curNode.data;
    }

10.判断结点是否存在

 //从链表中查找指定位置元素是否存在
    public boolean contains(T data) {
        Node curNode = this.head.next;
        while (curNode != null) {
            if (curNode.data.equals(data)) {
                return true;
            }
        }
        return false;
    }

11.删除结点

（1）删除头结点

 //从链表的头部删除元素
    public T removeHead() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> delNode = this.head.next;
        this.head.next = delNode.next;
        delNode.next = null;
        //更新size;
        this.size--;
        return delNode.data;
    }

（2）删除尾节点

//链表的尾部删除元素
    public T removeTail() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> pre = this.head;
        while (pre.next.next != null) {
            pre = pre.next;
        }
        Node<T> delNode = pre.next;
        pre.next = delNode.next;
        delNode.next = null;
        //更新size;
        this.size--;
        return delNode.data;
    }

（3）在指定位置删除结点

//删除任意位置的结点
    public T remove(int index){
        if(index<0||index>=this.size){
            throw new IllegalArgumentException("index is invalid");
        }
        //找删除结点的前驱
        Node<T>pre=this.head;
        int i=0;
        while(i<index){
            pre=pre.next;
            i++;
        }
        Node<T>delNode=pre.next;
        pre.next=delNode.next;
        delNode.next=null;
        this.size--;
        return delNode.data;
    }

（4）删除元素

//根据值从链表中删除元素
    public int removeByValue(T value){
        int count=0;
        //定义前驱结点
        Node<T>pre=this.head;
        while(pre.next!=null){
            Node curNode=pre.next;
            if(curNode.data.equals(value)){
                pre.next=pre.next.next;
                curNode.next=null;
                this.size--;
                count++;
            }else{
                pre=pre.next;
            }
        }
        return count;
    }

（5）不使用虚拟节点删除

//不使用虚拟头结点
    public int removeByValue2(T val){
        int count = 0;
        Node<T> realHead = this .head.next;

        while(realHead!=null&&realHead.data.equals(val)){
            realHead=realHead.next;
            this.size--;
            count++;
        }

        //判断链表是否为空
        if(realHead==null){
            return count;
        }

        //头结点不是删除的点
        Node pre = realHead;
        while(pre.next!=null){
            Node<T> delNode = pre.next;
            if(delNode.equals(val)){
                pre.next = delNode .next;
                delNode.next = null;
                this.size--;
                count++;
            }else{
                pre = pre .next;
            }
        }
        return count;
    }

三、完整代码

package com.algo.lesson.lesson03;

import java.util.Optional;
import java.util.Random;

public class SelfLinkedList<T> {
    //使用内部类——创建结点
    class Node<T> {
        T data;//节点本身
        Node next;//指向下个节点

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

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

    }

    //链表相关的属性和方法
    private Node head;//头结点
    private int size;//表示链表中有多少个结点

    public SelfLinkedList() {
        //创建一个虚拟头结点
        Node dummyHead = new Node(Integer.MIN_VALUE);
        this.head = dummyHead;
        this.size = 0;

        dummyHead.next = head;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    //向链表中添加结点
    //在头部添加
    public void addHead(T data) {
        /*//创建一个节点
        Node node= new Node(data);
        //挂接
        node.next=this.head;
        this.head=node;
        //更新size
        this.size++;*/
        add(0, data);
    }

    //在尾部添加
    public void addTail(T data) {
        /*Node node=new Node(data);
        //针对空链表做处理
        if(this.head==null){
            this.head=node;
            this.size++;
            return;
        }
        Node curNode=this.head;
        while(curNode.next!=null){
            curNode=curNode.next;
        }
        curNode.next=node;
        this.size++;*/
        add(this.size, data);
    }

    //在任意位置添加
    public void add(int index, T data) {
        //判断index是否有效
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("index is invalid");
        }
        //创建一个节点
        Node node = new Node(data);
        //特殊处理1：如果索引为0,
        if (index == 0) {
            this.head = new Node(data, this.head);
            this.size++;
            return;
        }
        //特殊处理2：链表为空（异常已抛出）
        //找前驱结点，从头开始找，让索引移动index-1次
        Node pre = this.head;
        for (int i = 1; i <= index; i++) {
            pre = pre.next;
        }
        //开始进行结点的挂接
        node.next = pre.next;
        pre.next = node;
        this.size++;
    }

    //打印整个链表
    @Override
    public String toString() {
        //从this。head开始一直向后
        Node curNode = this.head.next;
        StringBuilder sb = new StringBuilder();
        while (curNode != null) {
            sb.append(curNode.data + "-->");
            curNode = curNode.next;
        }
        sb.append("null");
        return sb.toString();
    }

    //从链表中查找指定位置元素是否存在
    public boolean contains(T data) {
        Node curNode = this.head.next;
        while (curNode != null) {
            if (curNode.data.equals(data)) {
                return true;
            }
        }
        return false;
    }

    //获取链表中元素的个数
    public int getSize() {
        return this.size;
    }

    //获取链表的头结点
    public Optional getFirst() {
        if (this.head.next == null) {
            return Optional.empty();
        }
        return Optional.ofNullable(this.head.next.data);
    }

    //获取链表的尾结点
    public Optional getLast() {
        if (this.head.next == null) {
            return Optional.empty();
        }
        Node<T> curNode = this.head;
        while (curNode.next != null) {
            curNode = curNode.next;
        }
        return Optional.of(curNode.data);
    }

    //从链表中获取任意位置的结点
    public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("index is invalid");
        }
        Node<T> curNode = this.head.next;
        int i = 0;
        while (i < index) {
            curNode = curNode.next;
            i++;
        }
        return curNode.data;
    }

    //从链表的头部删除元素
    public T removeHead() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> delNode = this.head.next;
        this.head.next = delNode.next;
        delNode.next = null;
        //更新size;
        this.size--;
        return delNode.data;
    }

    //链表的尾部删除元素
    public T removeTail() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> pre = this.head;
        while (pre.next.next != null) {
            pre = pre.next;
        }
        Node<T> delNode = pre.next;
        pre.next = delNode.next;
        delNode.next = null;
        //更新size;
        this.size--;
        return delNode.data;
    }

    //删除任意位置的结点
    public T remove(int index){
        if(index<0||index>=this.size){
            throw new IllegalArgumentException("index is invalid");
        }
        //找删除结点的前驱
        Node<T>pre=this.head;
        int i=0;
        while(i<index){
            pre=pre.next;
            i++;
        }
        Node<T>delNode=pre.next;
        pre.next=delNode.next;
        delNode.next=null;
        this.size--;
        return delNode.data;
    }

    //根据值从链表中删除元素
    public int removeByValue(T value){
        int count=0;
        //定义前驱结点
        Node<T>pre=this.head;
        while(pre.next!=null){
            Node curNode=pre.next;
            if(curNode.data.equals(value)){
                pre.next=pre.next.next;
                curNode.next=null;
                this.size--;
                count++;
            }else{
                pre=pre.next;
            }
        }
        return count;
    }

    //不使用虚拟头结点
    public int removeByValue2(T val){
        int count = 0;
        Node<T> realHead = this .head.next;

        while(realHead!=null&&realHead.data.equals(val)){
            realHead=realHead.next;
            this.size--;
            count++;
        }

        //判断链表是否为空
        if(realHead==null){
            return count;
        }

        //头结点不是删除的点
        Node pre = realHead;
        while(pre.next!=null){
            Node<T> delNode = pre.next;
            if(delNode.equals(val)){
                pre.next = delNode .next;
                delNode.next = null;
                this.size--;
                count++;
            }else{
                pre = pre .next;
            }
        }
        return count;
    }