java 单向链表和双向链表

java的单向链表~其实和c的链表思想差不多

package com.oracle.test; import java.util.Iterator; public class SingleLink implements Iterable{ private int size; private Node first;//首节点 /** * * 节点内部类 * */ private class Node{ Object data; Node next; public Node(Object data,Node next){ this.data=data; this.next=next; } } /** * 根据指定索引查找节点 * @param index * @return */ private Node node(int index){ Node c=first; for(int i=0;i<index;i++){ c=c.next; } return c; } /** * 添加方法 * @param obj */ public void add(Object obj){ Node newNode=new Node(obj,null); if(first==null){ first=newNode; }else{ Node last=node(size-1); last.next=newNode; } size++; } public Object get(int index){ this.checkIndex(index); return node(index).data; } public void del(int index){ this.checkIndex(index); Node last=node(index-1); last.next=last.next=last.next.next; size--; } /** * 检查下标是否正确的方法 * @param index */ private void checkIndex(int index){ if(index<0){ throw new IndexOutOfBoundsException("is negative number! "+index); } if(index>=size){ throw new IndexOutOfBoundsException("index out of bounds "+index); } } /** * 返回大小的方法 * @return */ public int size(){ return size; } private class Iter implements Iterator{ private Node cNode=first; private int cursor=0; @Override public boolean hasNext() { return cursor!=size; } @Override public Object next() { Object o=cNode.data; cNode=cNode.next; cursor++; return o; } } @Override public Iterator iterator() { return new Iter() ; } /** * 在指定位置插入一个新的节点 * @param obj */ public void insert(Object obj,int index){ this.checkIndex(index); if(index==0){ Node newNode=new Node(obj,first); first=newNode; }else{ Node target=node(index); Node newNode=new Node(obj,target); Node pre=node(index-1); pre.next=newNode; } size++; } }

测试：

package com.oracle.test; import java.util.Iterator; public class TestLink { public static void main(String[] args) { SingleLink sl=new SingleLink(); sl.add("aa"); sl.add("bb"); sl.add("cc"); for(int i=0;i<sl.size();i++){ System.out.println(sl.get(i)); } sl.insert("xxx",1); sl.del(2); //System.out.println(sl.get(2)); // for(Object o:sl){ // System.out.println(o); // } System.out.println("=========="); Iterator it=sl.iterator(); while(it.hasNext()){ System.out.println(it.next()); } //System.out.println(sl.get(-100)); } }

运行截图：

其实双向链表没有改变都少，就是多加了一个向前的指针

package com.oracle.test; import java.util.Iterator; public class DoubleLink implements Iterable{ private int size; private Node first;//首节点 /** * * 节点内部类 * */ private class Node{ Object data; Node next; Node pre; public Node(Object data,Node next,Node pre){ this.data=data; this.next=next; this.pre=pre; } } /** * 根据指定索引查找节点 * @param index * @return */ private Node node(int index){ Node c=first; for(int i=0;i<index;i++){ c=c.next; } return c; } /** * 添加方法 * @param obj */ public void add(Object obj){ Node newNode=new Node(obj,null,null); if(first==null){ first=newNode; }else{ Node last=node(size-1); newNode.pre=last; newNode.next=last.next; last.next=newNode; } size++; } public Object get(int index){ this.checkIndex(index); return node(index).data; } public void del(int index){ this.checkIndex(index); Node last=node(index-1); last.next=last.next.next; size--; } /** * 检查下标是否正确的方法 * @param index */ private void checkIndex(int index){ if(index<0){ throw new IndexOutOfBoundsException("is negative number! "+index); } if(index>=size){ throw new IndexOutOfBoundsException("index out of bounds "+index); } } /** * 返回大小的方法 * @return */ public int size(){ return size; } private class Iter implements Iterator{ private Node cNode=first; private int cursor=0; @Override public boolean hasNext() { return cursor!=size; } @Override public Object next() { Object o=cNode.data; cNode=cNode.next; cursor++; return o; } } @Override public Iterator iterator() { return new Iter() ; } /** * 在指定位置插入一个新的节点 * @param obj */ public void insert(Object obj,int index){ this.checkIndex(index); if(index==0){ Node newNode=new Node(obj,first,null); first=newNode; }else{ Node target=node(index); Node newNode=new Node(obj,target,null); target.pre.next=newNode; newNode.pre=target.pre; target.pre=newNode; } size++; } }

测试代码跟单向的都是一样，结果也是一样。