一.链表带哨兵
import java.util.Iterator;import java.util.function.Consumer;//带哨兵public class shuju02 implements Iterable {//整体 private Node head=new Node(666,null);//头指针 @Override public Iterator iterator() { //匿名内部类->带名字的内部类 return new NodeIterator(); } private class NodeIterator implements Iterator { Node p=head.next; @Override public boolean hasNext() {//是否有下一个元素 return p!=null;//不空返回真 } @Override public Integer next() {//返回当前值,并指向下一个元素 int v=p.value; p=p.next; return v; } } private static class Node { int value;//值 Node next;//下一个节点指针 public Node(int value, Node next) { this.value = value; this.next = next; } } public void addFirst(int value) throws IllegalAccessException { //1.链表为空 // head=new Node(value,null); //2.链表非空(头插) /* head = new Node(value, head);*/ insert(0,value); } //遍历链表 //Params:consumer-要执行的操作 public void loop(Consumer consumer) { Node p = head; while (p != null) { consumer.accept(p.value); p = p.next; } } //遍历链表2 //Params:consumer-要执行的操作 public void loop2(Consumer consumer) { for (Node p = head; p != null; p = p.next){ consumer.accept(p.value); } } //遍历链表3(递归遍历) //Params:consumer-要执行的操作 public void loop3(Consumerbefore,//没有哨兵 Consumerafter){ recursion(head,before,after); } private void recursion(Node curr,//当前节点 Consumerbefore,Consumerafter){//某个节点要进行的操作 if(curr==null){ return; } before.accept(curr.value); recursion(curr.next,before,after);//放前边倒叙,放后面顺序->指这句话 after.accept(curr.value); } private Node findLast(){ Node p; for(p=head;p.next!=null;p=p.next){ } return p; } public void addLast(int value){ Node last=findLast(); last.next=new Node(value,null); } /* public void test(){ int i=0; for(Node p=head;p!=null;p=p.next,i++){ System.out.println(p.value+"索引是:"+i); } 根据索引查找Params:index-索引Returns:找到，返回该索引位置节点的值Throws:IlLegalArgumentException-找不到，抛出index非法异常 }*/ private Node findNode(int index){//给定索引位置 int i=-1; for(Node p=head ;p!=null;p=p.next,i++){ if(i==index){ return p; } } return null;//没找到 } public int get(int index) throws IllegalAccessException { Node node=findNode(index); if(node==null){ //抛异常 illegalIndex(index); } return node.value; } //异常处理(重点) private static void illegalIndex(int index) throws IllegalAccessException { throw new IllegalAccessException( String.format("index[%d] 不合法%n", index) ); } /*向索引位置插入 */ public void insert(int index,int value) throws IllegalAccessException { Node prev=findNode(index-1);//找到上一个节点 if(prev==null){ illegalIndex(index); } prev.next=new Node(value,prev.next); } //1.问题 //删除头节点 public void removeFirst() throws IllegalAccessException { remove(0); } public void remove(int index) throws IllegalAccessException { Node prev=findNode(index-1);//上一个节点 if(prev==null){ illegalIndex(index); } Node removed=prev.next;//被删除的节点 if(removed==null){ illegalIndex(index); } prev.next=removed.next; }}二.双向链表带哨兵
import java.util.Iterator;//双向链表,带哨兵public class shuju03 implements Iterable{static class Node{ Node prev;//上一个节点指针 int value; Node next;//下一个节点指针 public Node(Node prev, int value, Node next) { this.prev = prev; this.value = value; this.next = next; }}private Node head;//头哨兵private Node tail;//尾哨兵 public shuju03(){ head=new Node(null,666,null); tail=new Node(null,666,null); head.next=tail; tail.prev=head; } private Node findNode(int index){ int i=-1; for(Node p=head;p!=tail;p=p.next,i++){ if(i==index){ return p; } } return null; } public void addFirst(int value) throws IllegalAccessException { insert(0,value); } public void removeLast() throws IllegalAccessException { Node removed=tail.prev; if(removed==head){ illegalIndex(0); } Node prev=removed.prev; prev.next=tail; tail.prev=prev; } public void addLast(int value){ Node last=tail.prev; Node added=new Node(last,value,tail); last.next=added; tail.prev=added; } public void insert(int index,int value) throws IllegalAccessException { Node prev=findNode(index-1); if(prev==null){ illegalIndex(index); } Node next=prev.next; Node inserted=new Node(prev,value,next); prev.next=inserted; next.prev=inserted; } public void remove(int index) throws IllegalAccessException { Node prev=findNode(index-1); if(prev==null){ illegalIndex(index); } Node removed=prev.next; if(removed==tail){ illegalIndex(index); } Node next=removed.next; prev.next=next; next.prev=prev; } private static void illegalIndex(int index) throws IllegalAccessException { throw new IllegalAccessException( String.format("index[%d] 不合法%n", index) ); } @Override public Iterator iterator() { return new Iterator() { Node p=head.next; @Override public boolean hasNext() { return p!=tail; } @Override public Integer next() { int value=p.value; return value; } }; }}三.双向链表
import java.util.Iterator;public class shuju04 implements Iterable { @Override public Iterator iterator() { return new Iterator() { Node p=sentinel.next; @Override public boolean hasNext() { return p!=sentinel; } @Override public Integer next() { int value= p.value; p=p.next; return value; } }; } /* s->1->2->3->1->s */ private static class Node{ Node prev; int value; Node next; public Node(Node prev, int value, Node next) { this.prev = prev; this.value = value; this.next = next; } } private Node sentinel=new Node(null,-1,null); public shuju04(){ sentinel.prev=sentinel; sentinel.next=sentinel; } //添加到第一个 //Params value-待添加值 public void addFirst(int value){ Node a=sentinel; Node b=sentinel.next; Node added=new Node(a,value,b); a.next=added; b.prev=added; } //添加到最后一个 //Params:value-待添加值 public void addLast(int value){ Node a=sentinel.prev; Node b=sentinel; Node added=new Node(a,value,b); a.next=added; b.prev=added; } //删除第一个 public void removeFirst() { Node removed=sentinel.next; if(removed==sentinel){ throw new IllegalArgumentException("非法"); } Node a=sentinel; Node b=removed.next; a.next=b; b.prev=a; } //删除最后一个 public void removeLast(){ Node removed=sentinel.prev; if(removed==sentinel){ throw new IllegalArgumentException("非法"); } Node a=removed.prev; Node b=sentinel; a.next=b; b.prev=a; } //根据值删除 // Params:value-目标值 public void removeByValue(int value){ Node removed=findByValue(value); if(removed==null){ return;//不用删 } Node a=removed.prev; Node b=removed.next; a.next=b; b.prev=a; } private Node findByValue(int value){ Node p=sentinel.next; while(p!=sentinel){ if(p.value==value){ return p; } p=p.next; } return null; }}