内部类 ，未使用内部类的链表可以点击名字查看。
此篇文章主要介绍运用内部类的Java链表的写法。
链表正如其名，就像一个一个珠子被串起来，只有前一个珠子和后一个珠子和当前珠子有关系，是一种一对一的数据结构。
这样的数据结构，在插入和删除节点的时候，会显的特别方便，因为不像数组一样要移动大量的元素，而只需要改变一些引用就可以实现增删。
链表的增加
1)头插法
顾名思义头插法及每次插入都是插入到第一个节点处
链表的头插法只需要两步（已经New出了新节点）
1.将1号元素的地址给插入的元素
2.将插入元素的地址给头结点
2）尾插法
链表的尾插法只需要一步（已经New出了新节点）
将插入元素的地址给最后一个元素。
3）插入到指定位置
插入到指定位置和头插法原理基本相同，不过是把插入位置之前的元素当做头结点，其插入进行的操作基本相同，只是需要提前找到相应的位置。
链表的删除
未完待续
链表的遍历
链表的遍历只需要一直移动引用，使得临时引用变量一直向后移动，直到临时引用变量为null，即已经遍历完了所有元素。
链表的长度
原理和遍历相同，只是将基本操作变为计数，切最后将结果return出去。
代码
package com.chenxixuexi;
/**
* 链表
* @author 焦焱
*
*/
public class Link1 {
private Entry head = new Entry(); //指向头结点的引用
/**
* 节点类
* @author 焦焱
*
*/
class Entry{//Entry Node
int data;
Entry next;
/**
* 头结点空构造方法
*/
public Entry() {
data = 0;
next = null;
}
/**
* 构造节点
* @param a
*/
public Entry(int a) {
data = a;
next = null;
}
}
/**
* 头插法
* @param val 需要插入的数据
*/
public void insertHead(int val)
{
//有这么一个节点
Entry cur = new Entry(val);
cur.next = head.next;
head.next = cur;
}
/**
* 尾插法
* @param val 需要插入的值
*/
public void insertTail(int val)
{
Entry cur = head;
while(cur.next!= null) //循环直到cur.next为空 把cur弹出
{
cur = cur.next;
}
cur.next = new Entry(val);//给cur.next 赋值为新节点的地址
}
/**
* 插入到pos位置 从有数据开始为0下标
* @param pos 位置序号
* @param val 插入的值
*/
public void insertPos(int pos,int val)
{
Entry cur = head; //获取头结点
int count = 0;
if(pos<0||pos>getLength()) //如果需要中断操作，只需要在此return即可
System.out.println("下标"+pos+"不合法,自动插入到最后位置");
while(cur.next!= null) //循环直到cur.next为空 把cur弹出 及如果没找到就会把元素插入到最后面
{
if(count == pos)
break;
count++;
cur = cur.next;
}
Entry cur1 = new Entry(val);
cur1.next = cur.next;
cur.next = cur1;
}
/**
* 遍历输出数组
*/
public void show()
{
Entry cur = head.next; //获取到第一个节点
System.out.print("[");
while(cur!=null) //如果cur不是null
{
System.out.print(cur.data+" "); //输出
cur = cur.next; //向下递进
}
System.out.println("]");
}
/**
* 获得链表长度
* @return 链表长度
*/
public int getLength()
{ int count=0;
Entry cur = head.next; //获取到第一个节点
while(cur!=null) //如果cur不是null
{
count++; //计数
cur = cur.next; //向下递进
}
return count;
}
}
翻转链表
通过翻转节点实现链表的翻转。
public void Reversal()
{
Entry<T> p = head.next,p1 = null,p2 = null;
while(p!=null){
p1 = p.next; //设置p1是p结点的后继结点,用p1来保持p的后继结点
p.next = p2; //链接,使p.next指向p结点的前一个结点
p2 = p; //p2向后移一步
p = p1; //p向后移一步
}
head.next = p2; //head.next指向最后一个结点
}
求单链表倒数第K节点
/**
* 求倒数第K个元素
*
* @param k 序号
* @return 所求元素
*/
public int BackWardsToK(int k)
{
if(k>getLength()-1){ //判错
System.err.println("超越限制,下标不合法，倒数下标从0开始");
return 0;
}
int key = getLength()-k;
Entry<T> cur = head; //获取头结点
int count = 0;
while(cur.next!= null) //循环直到cur.next为空 把cur弹出 及如果没找到就会把元素插入到最后面
{
if(count == key)
break;
count++;
cur = cur.next;
}
return cur.data;
}
其原理很简单，倒数第K个，及为第length-k个元素，只需要循环取到第length-k个元素即可。