数据结构之单链表java实现

基本概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中指针链接次序实现的。和数组相比较，链表不需要指定大小，也不需要连续的地址。
单链表的基本设计思维是，利用结构体的设置，额外开辟一个空间去做指针，指向下一个结点。
在这里插入图片描述
其中，DATA是需要存储的数据元素，可以为任何数据格式，可以是数组，可以是int，还可以是结构体。
NEXT作为一个空指针，其代表了一个可以指向的区域，通常是用来指向下一个结点，链表尾部NEXT指向NULL（空），因为尾部没有任何可以指向的空间了。

创建结点

private static class Node<E> {private E item; private Node<E> next;Node(E element,Node<E> next){item = element;this.next = next;}
}

创建接口```java
public interface BaseTab<T> {/*** 空置链表*/public void clear();/*** 判断链表是否为空* @return true 为空*/public boolean isEmpty();//获取链表中的元素个数public int length();//获取并返回线性表中的第i个元素public T get(int i);//添加一个元素public void insert(T t);//向第i个元素之前插入一个元素public void insert(int i,T t);//删除并返回第i个元素public T remove(int i);//返回指定元素的序号，若不存在返回-1public int indexOf(T t);
}

实现全部功能

public class SingleLinkedList<E> implements BaseTab<E>{private Node<E> mHeader; //链表头部结点,头部结点不存储数据，只存储nextprivate int size = 0; //记录链表长度public SingleLinkedList(){}@Overridepublic void clear() {mHeader.next = null;size = 0;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic int length() {return size;}@Overridepublic E get(int index) {Node<E> node = mHeader;//从Header开始循环for(int i = 0;i < index;i++){node = node.next;}return node.item;}@Overridepublic void insert(E data) {if(mHeader == null){mHeader = new Node<E>(data,null);size++;return;}Node<E> lastNode = mHeader;while (lastNode.next != null){ //通过循环找到链表的尾部lastNode = lastNode.next;}lastNode.next = new Node<>(data,null);size++;}@Overridepublic void insert(int index, E data) {//创建新的结点用来存放数据if(mHeader == null){mHeader = new Node<E>(data,null);size++;return;}Node<E> newNode = new Node<E>(data,null);Node<E> preNode = mHeader;for(int i = 0;i <= index -1;i++){ //循环找到index位置的前一个结点preNode = mHeader.next;}newNode.next = preNode.next;preNode.next = newNode;size++;}/*** 打印出链表所有数据*/public void printAll(){Node<E> node = mHeader;while (node.next != null){System.out.println(node.item);node = node.next;}System.out.println(node.item);}@Overridepublic E remove(int index) {//1.找到指定位置的前一个NodeNode<E> preNode = mHeader;for(int i = 0; i < index -1;i++){preNode = preNode.next;}//需要被删除的NodeNode<E> removeNode = preNode.next;preNode.next = removeNode.next;size--;return removeNode.item;}@Overridepublic int indexOf(E data) {Node node = mHeader;for(int i = 0;i < size;i++){if(node.item.equals(data)){return i;} else {node = node.next;}}return -1;}private static class Node<E> {private E item;private Node<E> next;Node(E element,Node<E> next){item = element;this.next = next;}}
}

反转链表

链表反转是一道比较常见的面试题
eg：链表中输入0，1，2，3，4，输出 4，3，2，1，0
在这里插入图片描述
实现一个结点：

public class Node<T> {T data; //数据Node<T> next; //指向下一个结点public Node(T value){data = value;}
}

从结点的结构上面来说，我们需要修改的是next，将next由指向下一个改成指向上一个。
链表全部反转，那就需要从尾部或者头部开始，从尾部开始的话，使用递归的思想。

    public static <T> Node<T> reversalLink(Node<T> head){//主要是通过head.next == null 找出最后面的一个结点if(head == null || head.next == null) return head;//通过递归找到最后的一个作为Head//递归执行顺序是4，3，2，1，0Node<T> revHead = reversalLink(head.next);//调整指针//eg:执行到3时需要做以下操作//1.4的next应该是3，当head = 3时， 目前head.next = 4 4.next = head，就将4的下一个结点指向3head.next.next = head;//执行上上一步后，3->4,4->3,现在需要将3->4断开head.next = null;return revHead;}public static void main(String[] args) {Node<Integer> head = new Node<>(0);Node<Integer> node1 = new Node<>(1);Node<Integer> node2 = new Node<>(2);Node<Integer> node3 = new Node<>(3);Node<Integer> node4 = new Node<>(4);head.next = node1;node1.next = node2;node2.next = node3;node3.next = node4;//反转前Node<Integer> node = head;while (node != null){System.out.print(node.data + " ");node = node.next;}System.out.println("");System.out.println("-----反转后-------");Node<Integer> revHead = reversalLink(head);while (revHead != null){System.out.print(revHead.data + " ");revHead = revHead.next;}}

从链表头部开始
在这里插入图片描述
思路就如上面所画，从header开始，拆成两个链表

    public static <T> Node<T> reversalLink1(Node<T> head){Node<T> preNode = null;Node<T> curNode = head;while (curNode != null){Node<T> nextNode = curNode.next;curNode.next = preNode;preNode = curNode;curNode = nextNode;}return preNode;}