資料結構鏈表的基本操作

/*資料結構單向鏈表基本操作
節點類
 */

import java.util.Iterator;
import java.util.function.Consumer;

public class shujujiegou implements Iterable<Integer> {//整體
    private Node head;//頭指標

    @Override
    public Iterator<Integer> iterator() {
        //匿名內部類->帶名字的內部類
        return new NodeIterator();
    }
    private class NodeIterator implements Iterator<Integer> {
        Node p=head;

        @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 = https://www.cnblogs.com/3-6-8/p/value;
            this.next = next;
        }
    }

    public void addFirst(int value) {
        //1.鏈表為空
        // head=new Node(value,null);
        //2.鏈表非空(頭插)
        head = new Node(value, head);
    }
//遍歷鏈表
    //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);
        }
    }

    private Node findLast(){
        if(head==null){
            return null;
        }
        Node p;
        for(p=head;p.next!=null;p=p.next){

        }
        return p;
    }
    public void addLast(int value){
        Node last=findLast();
        if(last==null){
            addFirst(value);
            return;
        }
        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=0;
        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 {
        if(index==0){
            addFirst(value);
            return;
        }
        Node prev=findNode(index-1);//找到上一個節點
        if(prev==null){
            illegalIndex(index);
        }
        prev.next=new Node(value,prev.next);

    }
//1.問題
    //洗掉頭節點
    public void removeFirst() throws IllegalAccessException {
        if(head==null) {
             illegalIndex(0);
        }
        head=head.next;
    }
    public void remove(int index) throws IllegalAccessException {
        if(index==0){
            removeFirst();
            return;
        }
        Node prev=findNode(index-1);//上一個節點
        if(prev==null){
            illegalIndex(index);
        }
        Node removed=prev.next;//被洗掉的節點
        if(removed==null){
            illegalIndex(index);
        }
        prev.next=removed.next;

    }
}

標籤：其他

上一篇：二分查找

下一篇：返回列表