Java实现单向链表

• • 单向链表的特点
  • • 主要属性及方法
    • • size
      • 节点类Node
      • 方法
      • • 节点的添加
        • 节点的删除
        • 节点数据的获取
        • 链表的遍历
  • 实现细节
  • • • 测试

单向链表，见名知意，即单向存储的链表。由一个个节点链接而成，每个节点保存当前节点存储的数据以及下一个节点的位置（由于java中淡化了指针这个概念，此处我们可以理解为保存下一个节点）每个节点只知道后继节点是谁，而不清楚自己的上一个前驱节点（就像间谍一样，老大能找到你，但你不能去找老大）

代表链表中节点的数量

属性：T data、Node next

添加元素到头、尾结点、指定位置

删除头、尾、指定位置的节点

public class SingleList {
    private int size;
    private Node head;
    private Node tail;

    public int getSize() {
        return size;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public Node getTail() {
        return tail;
    }

    public void setTail(Node tail) {
        this.tail = tail;
    }

    private static class Node{
        private T data;
        private Node next;

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

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

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    
    boolean addFirst(T data) {
        Node node = new Node<>(data);
        if (head == null){
            head = node;
            tail = node;
        }else {
            node.setNext(head);
            head = node;
        }
        size++;
        return true;
    }

    
    boolean addLast(T data) {
        Node node = new Node<>(data);
        if (head == null){
            head = node;
        }else {
            tail.next = node;
        }
        tail = node;
        size++;
        return true;
    }

    
    public boolean add(int index, T data) {
        Node node = new Node<>(data);
        //定位到指定位置,注意，此处右边界实际上是取不到size的，因为下标从0开始，但是插入的位置可以是size
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "tsize:" + size);
        } else if (index == 0) {
            return addFirst(data);
        } else if(index == size){
            tail.next = node;
            tail = node;
        }else {
            Node temp = head;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            node.setNext(temp.next);
            temp.setNext(node);
        }
        size++;
        return true;
    }

    
    public T removeFirst() {
        if (head == null) {
            throw new RuntimeException("该链表为空！");
        } else {
            T data = head.data;
            head = head.next;
            size--;
            return data;
        }
    }

    
    public T removeLast() {
        T data;
        if (head == null) {
            throw new RuntimeException("该链表为空！");
        } else if (head == tail){
            data = head.data;
            head = null;
            tail = null;
        }else {
            Node temp = head;
            while (temp.next != tail){
                temp = temp.next;
            }
            data = tail.data;
            tail = temp;
        }
        size--;
        return data;
    }

    
    public T remove(int index) {
        //定位到指定位置
        T data;
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "tsize:" + size);
        } else if (index == 0) {
            return removeFirst();
        } else if(index == size-1){
            return removeLast();
        }else {
            Node temp = head;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            Node old = temp.next;
            temp.next = temp.next.next;
            data = old.data;
        }
        size--;
        return data;
    }

    
    public T getData(int index){
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "tsize:" + size);
        }else {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.getNext();
            }
            return node.getData();
        }
    }

    
    public void print() {
        if (size == 0) {
            System.out.println("该链表为空!");
        }else {
            Node node = head;
            while (node != null) {
                System.out.print(node.data+ "t");
                node = node.next;
            }
            System.out.println();
        }
    }
}

添加元素方法

public class Test {
    public static void main(String[] args) {
        //实例化单链表对象
        SingleList singleList = new SingleList<>();

        //添加到尾结点
        singleList.addLast(1);
        singleList.addLast(3);

        //添加头尾结点
        singleList.addFirst(0);

        //添加到指定下标元素
        singleList.add(2,2);
        //测试打印输出
        singleList.print();
    }
}

//获取指定下标的数据值
Integer data = singleList.getData(0);
System.out.println("下标为0的节点存放的数据是—->"+data);

//删除头结点
singleList.removeFirst();
singleList.print();
System.out.println("==========================");

//删除尾结点
singleList.removeLast();
singleList.print();
System.out.println("==========================");

//删除指定下标对应得节点
singleList.remove(1);
singleList.print();

以上均为本人个人观点，借此分享，希望能和大家一起进步。如有不慎之处，劳请各位批评指正！鄙人将不胜感激并在第一时间进行修改！