链式线性表将采用一组地址任意的存储单元存放线性表中的数据元素。链式结构的线性表不会按线性的逻辑顺序保存数据元素，它需要在每一个数据元素里保存一个指向下一个数据元素的引用。
链式结构克服了顺序结构需要预先知道数据大小的缺点，可以充分利用计算机的内存空间，实现内存的动态分配。在插入和删除操作上，比顺序结构简单，但是失去了顺序结构的随机存取特性，并且由于每个节点增加了一个引用，所以空间开销也比较大。
package Algorithms;public class LinkList<T> {//定义内部类Node，Node实例代表链表的节点private class Node{private T data;//保存节点的数据private Node next;//保存下个节点的引用public Node() {//无参数的构造器}public Node(T data, Node next) {//初始化全部参数的构造器this.data = data;this.next = next;}}private Node header;//保存链表的头结点private Node tail;//保存链表的为节点private int size;//保存链表中已包含的节点数public LinkList() {//创建空链表header = null;tail = null;}public LinkList(T element){//以指定数据元素来创建链表，该链表中只有一个元素header = new Node(element,null);tail = header; //只有一个节点，header和tail的值相同size++;}public int length(){//返回链表的长度return size;}public T get(int index){//根据链表索引来获取节点的数据return (T) getNodeByIndex(index).data;}private Node getNodeByIndex(int index){//根据索引来获取指定位置的节点，找不到返回nullif(index<0||index>size-1)throw new IndexOutOfBoundsException("线性表索引出界");Node current = header;for(int i=0;i<size&¤t != null;i++,current = current.next)if(i==index)return current;return null;}public int locate(T element){//根据数据的值在链表中查找该节点的索引，找不到则返回-1Node current = header;for(int i=0;i<size&¤t != null;i++,current=current.next)if(current.data.equals(element))return i;return -1;}public void insert(T element,int index){//在链表的指定位置插入数据if(index<0||index>size)throw new IndexOutOfBoundsException("线性表索引出界");if(header==null)addAtTail(element);else{if(index==0)addAtHeader(element);else{Node prev = getNodeByIndex(index-1);Node newNode = new Node(element,prev.next);prev.next = newNode;size++;}}}public void addAtTail(T element){//采用尾插法为链表添加新节点if(header==null){header = new Node(element,null);tail = header;}else{Node newNode = new Node(element,null);tail.next = newNode;tail = newNode;}size++;}public void addAtHeader(T element){//采用头插法为链表添加新节点header = new Node(element,header);if(tail==null)tail = header;size++;}public T delete(int index){//删除链表中指定索引处的元素if(index<0||index>size-1)throw new IndexOutOfBoundsException("线性表索引出界");Node del = null;if(index==0){//如果被删除的是头结点，也就是不存在前一个节点del = header;header = header.next;}else{Node prv = getNodeByIndex(index-1);//获取删除点的前一个节点del = prv.next;prv.next = del.next;del.next = null;}size--;return del.data;}public T remove(){//删除链表中最后一个元素return delete(size-1);}public boolean isEmpty(){//判断链表是否为空链表return size==0;}public void clear(){//清空线性表header = null;tail = null;size = 0;}public String toString(){if(isEmpty())return "[]";StringBuilder sb = new StringBuilder("[");for(Node current=header;current!=null;current=current.next)sb.append(current.data.toString()+", ");int len = sb.length();return sb.delete(len-2, len).append("]").toString();}}
不要气馁于那前方的阴影，那只是因为我背后光芒万丈
