java中没有将指针暴露给用户（以前做过看过一篇文章写有java中是有指针的，只是被藏起来了），所以得使用引用的方式。
何为引用请看下面这篇文章（写的很不错，当然肯定比我写的好）：
https://www.cnblogs.com/huajiezh/p/5835618.html
链表中内部类和嵌套类的区别：
https://blog.csdn.net/WelcomeSpring/article/details/79430546
以下代码采用内部类。
/**
* 内部类
* @param <E> 泛型
*/
private class Node<E>{
E data;
Node<E> next;
Node<E> pre;
public Node(E data){
this.data=data;
} public Node(E data, Node next, Node pre) {
this.data = data;
this.next = next;
this.pre = pre;
}
public Node(){
next=null;
pre=null;
data=null;
}
public E getData() {
return data;
} public void setData(E data) {
this.data = data;
} public Node getNext() {
return next;
} public void setNext(Node next) {
this.next = next;
} public Node getPre() {
return pre;
} public void setPre(Node pre) {
this.pre = pre;
}
}
E data：存储对象的区域 Node<E> next:引用链表的下一个对象 Node<E> pre;引用链表的上一个对象 所构成了一个双链表
源代码：
/**
* @author 李正阳
* @param <E> 泛型
*/
public class MyLinkedList<E> implements List<E> { private Node<E> head=new Node<>();
private int size=0; /**
* 在链表的最后插入元素
* @param data 插入的元素
* @return true 插入成功
*/
@Override
public boolean add(E data) {
Node<E> pNode= head;
while (pNode.getNext()!=null){
pNode=pNode.next;
}
Node<E> temp=new Node(data);
temp.setPre(pNode);
pNode.setNext(temp);
size++;
return true;
} /**
*在number位置添加一个元素
* @param number 在链表中的位置（不是从0开始）
* @return true 添加成功
*/
@Override
public boolean add(int number,E data){
Node<E> pNode=head;
Node<E> temp=new Node<>(data);
for (int i=0;i<number;i++){
pNode= pNode.getNext();
}
pNode.getPre().setNext(temp);
temp.setPre(pNode.getPre());
temp.setNext(pNode.getNext());
pNode.getNext().setPre(temp);
return true;
}
/**
* 判空函数
* @return true 链表为空 false 链表不为空
*/
@Override
public boolean isEmpty() {
if(head.getNext()==null){
return true;
}else {
return false;
}
} /**
* 删除链表中number位置的元素
* @param number 元素在链表中的位置
* @return 删除的那个元素
*/
@Override
public E remove(int number) {
E temp;
Node<E> pNode,preNode;
pNode=head;
for(int i=0;i<number;i++){
pNode=pNode.next;
}
temp=(E) pNode.getData();
preNode=pNode.getPre();
preNode.setNext(pNode.getNext());
pNode.getNext().setPre(preNode);
pNode.setNext(null);
pNode.setPre(null);
pNode=null;
return temp;
} /**
* 尾删法
* @return 删除的那个元素
*/
@Override
public E remove() {
E temp;
Node<E> pNode,preNode;
pNode=head;
while (pNode.getNext()!=null){
pNode=pNode.next;
}
temp=(E) pNode.getData();
preNode=pNode.getPre();
preNode.setNext(null);
pNode.setNext(null);
pNode.setPre(null);
pNode=null;
return temp;
} /**
* 将第i位置的元素替换
* @param i 元素在链表中的位置
* @param data 替换的元素
*/
@Override
public void set(int i, E data) {
Node<E> pNode=head;
for (int j=0;j<i;j++){
pNode=pNode.getNext();
}
pNode.setData(data);
} /**
* 获得链表在i位置的元素
* @param i 元素在i位置的元素
* @return i位置的元素
*/
@Override
public E get(int i) {
E temp;
Node<E> pNode=head;
for (int j=0;j<i;j++){
pNode=pNode.getNext();
}
temp=(E) pNode.getData();
return temp;
} /**
* 检查这条链表现有的是否为回文
* @return true 为回文 false 不为回文
*/
@Override
public boolean isPalindrome() {
Node<E> pNode,nNode;
pNode=head.getNext();
nNode=head;
while (nNode.getNext()!=null){
nNode=nNode.getNext();
}
StringBuilder posSequence=new StringBuilder();
StringBuilder revOrder=new StringBuilder();
while(pNode.getNext()!=null) {
posSequence.append(pNode.getData());
pNode=pNode.getNext();
}
posSequence.append(pNode.getData());
while (nNode.getPre()!=null){
revOrder.append(nNode.getData());
nNode=nNode.getPre();
}
String posequence=posSequence.toString();
String revoredr=revOrder.toString();
if(posequence.equals(revoredr)) {
return true;
}else {
return false;
}
} /**
* 倒置链表
*/
@Override
public void reverseList(){
Node<E> node,nNode;
node=head.getNext();
node.setPre(node.getNext());
node=node.getNext();
nNode=node.getNext();
head.getNext().setNext(null);
while (nNode!=null) {
node.setNext(node.getPre());
node.setPre(nNode);
node=node.getPre();
nNode=node.getNext();
}
node.setNext(node.getPre());
node.setPre(head);
head.setNext(node);
}
/**
* 头插法
* @param data 插入的元素
* @return true 添加成功 false 添加失败
*/
@Override
public boolean addFirst(E data){
Node<E> node=new Node(data);
Node<E> preNode=head.getNext();
head.setNext(node);
preNode.setPre(node);
node.setNext(preNode);
node.setPre(head);
return true;
} /**
* 遍历并输出链表中的元素
*/
@Override
public void traver() {
if(isEmpty()){
System.out.println("链表为空");
}else {
Node<E> pNode = head.getNext();
while (pNode != null) {
System.out.print(pNode.getData() + " ");
pNode = pNode.getNext();
}
}
} /**
* 内部类
* @param <E> 泛型
*/
private class Node<E>{
E data;
Node<E> next;
Node<E> pre;
public Node(E data){
this.data=data;
} public Node(E data, Node next, Node pre) {
this.data = data;
this.next = next;
this.pre = pre;
}
public Node(){
next=null;
pre=null;
data=null;
}
public E getData() {
return data;
} public void setData(E data) {
this.data = data;
} public Node getNext() {
return next;
} public void setNext(Node next) {
this.next = next;
} public Node getPre() {
return pre;
} public void setPre(Node pre) {
this.pre = pre;
}
} }
检查链表所存储是否为回文：
/**
* 检查这条链表现有的是否为回文
* @return true 为回文 false 不为回文
*/
@Override
public boolean isPalindrome() {
Node<E> pNode,nNode;
pNode=head.getNext();
nNode=head;
while (nNode.getNext()!=null){
nNode=nNode.getNext();
}
StringBuilder posSequence=new StringBuilder();
StringBuilder revOrder=new StringBuilder();
while(pNode.getNext()!=null) {
posSequence.append(pNode.getData());
pNode=pNode.getNext();
}
posSequence.append(pNode.getData());
while (nNode.getPre()!=null){
revOrder.append(nNode.getData());
nNode=nNode.getPre();
}
String posequence=posSequence.toString();
String revoredr=revOrder.toString();
if(posequence.equals(revoredr)) {
return true;
}else {
return false;
}
}
* 算法设计：比较粗暴，直接从链表头到尾将值组成一个String
* 从链表尾到头将值组成一个String
* 然后比较这两个字符串是否相等
链表倒置：
/**
* 倒置链表
* 算法设计
*/
@Override
public void reverseList(){
Node<E> node,nNode;
node=head.getNext();
node.setPre(node.getNext());
node=node.getNext();
nNode=node.getNext();
head.getNext().setNext(null);
while (nNode!=null) {
node.setNext(node.getPre());
node.setPre(nNode);
node=node.getPre();
nNode=node.getNext();
}
node.setNext(node.getPre());
node.setPre(head);
head.setNext(node);
}
* 算法设计：倒置链表需要修改三处地方，
* 头结点变成尾节点:将pre赋值尾next的引用,next赋值为null
* 尾节点变成头结点：将next赋值为pre，pre赋值为null
* 中间节点将next设置为pre，next设置为pre