一,Node节点：
/**
* 存储元素基本单位
*/
public class Node {
Object data;
Node pre;
Node next; public Node(Node pre, Object data, Node next) {
this.data = data;
this.pre = pre;
this.next = next;
}
}
二.自己实现一个链表
public class MyLinkedList {
private Node first;
private Node last;
private int size;
public boolean isEmpty(){
return size==0;
}
public int size(){
return size;
}
public boolean addBy(Object data){
Node l=last;
Node entry=new Node(l,data,null);
last=entry;
if(l==null){
first=entry;
}else {
l.next=entry;
}
size++;
return true;
}
/**
* 根据下标获取Node元素
* 采用了二分查找法
* @param index
* @return
*/
private Node node(int index){
if(index<(size>>1)){
//下标在前半段,从前往后查
Node current=first;
for(int i=0;i<index;i++){
current=current.next;
}
return current;
}else {
//下标在后半段,从后往前查
Node current=last;
for (int i=size-1;i>index;i--){
current=current.pre;
}
return current;
}
}
/**
* 判断下标是否越界
* @param index
*/
private void checkRange(int index){
if(index>=size||index<0){
throw new IndexOutOfBoundsException("下标越界");
}
}
/**
* 根据下标获取元素
* @param index
* @return
*/
public Object get(int index){
checkRange(index);
return node(index).data;
}
private Object deleteNode(int index){
Node node=node(index);
Object data=node.data;
Node preNode=node.pre;
Node nextNode=node.next;
if(preNode==null){
//删除了第一个元素
first=nextNode;
}else {
preNode.next=nextNode;
node.next=null;
}
if(nextNode==null){
//删除了最后一个元素
last=preNode;
}else {
nextNode.pre=preNode;
node.pre=null;
}
size--;
node.data=null;
return data;
}
public Object remove(int index){
checkRange(index);
return deleteNode(index);
}
private void addBefore(Object data,Node specificNode){
Node preNode=specificNode.pre;
Node newNode=new Node(preNode,data,specificNode);
if(preNode==null) {
first=newNode;
}else {
preNode.next=newNode;
}
specificNode.pre=newNode;
size++;
}
public void add(int index,Object data){
checkRange(index);
if(index==size){
addBy(data);
}else {
Node node=node(index);
addBefore(data,node);
}
}
}