欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的方法

 更新時(shí)間：2022年01月13日 14:20:07   作者：胡安民  
這篇文章主要介紹了Java實(shí)現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的相關(guān)資料,每一個(gè)鏈表都包含多個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)又包含兩個(gè)部分，一個(gè)是數(shù)據(jù)域（儲(chǔ)存節(jié)點(diǎn)含有的信息），一個(gè)是引用域（儲(chǔ)存下一個(gè)節(jié)點(diǎn)或者上一個(gè)節(jié)點(diǎn)的地址），需要的朋友可以參考下

什么是鏈表？

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針連接次序?qū)崿F(xiàn)的。
每一個(gè)鏈表都包含多個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)又包含兩個(gè)部分，一個(gè)是數(shù)據(jù)域（儲(chǔ)存節(jié)點(diǎn)含有的信息），一個(gè)是引用域（儲(chǔ)存下一個(gè)節(jié)點(diǎn)或者上一個(gè)節(jié)點(diǎn)的地址）。

鏈表的理解示意圖:

在這里插入圖片描述

鏈表的特點(diǎn)是什么？

獲取數(shù)據(jù)麻煩，需要遍歷查找，比數(shù)組慢
方便插入、刪除

簡(jiǎn)單的鏈表的實(shí)現(xiàn)原理

創(chuàng)建一個(gè)節(jié)點(diǎn)類，其中節(jié)點(diǎn)類包含兩個(gè)部分，第一個(gè)是數(shù)據(jù)域（你到時(shí)候要往節(jié)點(diǎn)里面儲(chǔ)存的信息），第二個(gè)是引用域（相當(dāng)于指針，單向鏈表有一個(gè)指針，指向下一個(gè)節(jié)點(diǎn)；雙向鏈表有兩個(gè)指針，分別指向下一個(gè)和上一個(gè)節(jié)點(diǎn)）

創(chuàng)建一個(gè)鏈表類，其中鏈表類包含三個(gè)屬性：頭結(jié)點(diǎn)、尾節(jié)點(diǎn)和大小，方法包含添加、刪除、插入等等方法。 通用節(jié)點(diǎn)抽象類

package com.lineardatastructure.linked;
/**
 * @author huanmin
 * @param <T>
 */
/**
 * 自定義鏈表接口定義
 **/
public abstract class LinkedAbs<T> implements Iterable<T> {
    //列表長(zhǎng)度
    public int size = 0;
    //當(dāng)前節(jié)點(diǎn)
    public Node head;
    //尾節(jié)點(diǎn)
    public Node end;
    //節(jié)點(diǎn)
    protected class Node {
        Node previous = null;//上一個(gè)結(jié)點(diǎn)
        Node next = null;//下一個(gè)結(jié)點(diǎn)
        T data;//結(jié)點(diǎn)數(shù)據(jù)
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
        public Node(Node next, Node previous) {
            this.next = next;
            this.previous = previous;
        }
        public Node(T data, Node next, Node previous) {
            this.next = next;
            this.previous = previous;
        }
        public Node(T data) {
            this.data = data;
        }
    }
    /**
     * 判斷鏈表是否有環(huán)：
     * 有環(huán)返回環(huán)的入口節(jié)點(diǎn),沒(méi)有返回null
     * 設(shè)置快指針和慢指針，慢指針每次走一步，快指針每次走兩步
     * 當(dāng)快指針與慢指針相等時(shí)，就說(shuō)明該鏈表有環(huán),并且這個(gè)節(jié)點(diǎn)就是環(huán)的入口
     */
    public Node isRinged(){
        if(head == null){
            return null;
        }
          Node slow = head;
        Node fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return fast;
            }
        }
        return null;
    }
    // 獲取鏈表頭元素
    public T getFrom() {
        return head.data;
    }
    //獲取鏈表結(jié)尾元素
    public T getEnd() {
        return end.data;
    }
    //獲取鏈表中元素個(gè)數(shù)
    public int getSize() {
        return size;
    }
    /**
     * 判斷鏈表中是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 銷毀鏈表
     */
    public void stackDestroy() {
        head = null;
        size = 0;
        end=null;
    }
    //尋找單鏈表的中間結(jié)點(diǎn)：
    public  abstract T findMiddle();
    /**
     * 元素反轉(zhuǎn)
     */
    public abstract void reserveLink();
    /**
     * 獲取指定元素
     *
     * @param index
     */
    public abstract T get(int index);
    /**
     * 向鏈表中添加元素
     *
     * @param e
     */
    public abstract void addFirst(T e);
    public abstract void addlast(T e);
    public abstract void add(T e);
    /**
     * 從鏈表中刪除元素
     */
    public abstract boolean remove(T obj);
    public abstract boolean remove(int index);
    public abstract boolean removeFirst();
    public abstract boolean removeLast();
}

實(shí)現(xiàn)單向鏈表

在這里插入圖片描述

package com.lineardatastructure.linked;
import java.util.Iterator;
/**
 * @author huanmin
 * @param <T>
 */
// 單向鏈表
public class OneWayLinked<T> extends LinkedAbs<T> {
    @Override
    public void reserveLink() {
        Node curNode = head;//頭結(jié)點(diǎn)
        Node preNode = null;//前一個(gè)結(jié)點(diǎn)
        while(curNode != null){
            Node nextNode = curNode.next;//保留下一個(gè)結(jié)點(diǎn)
            curNode.next = preNode;//指針?lè)崔D(zhuǎn)
            preNode = curNode;//前結(jié)點(diǎn)后移
            curNode = nextNode;//當(dāng)前結(jié)點(diǎn)后移
        }
        head = preNode;
    }
    /**
     * 尋找單鏈表的中間結(jié)點(diǎn)：
     * 方法一、先求出鏈表的長(zhǎng)度，再遍歷1/2鏈表長(zhǎng)度，尋找出鏈表的中間結(jié)點(diǎn)
     * 方法二、：
     * 用兩個(gè)指針遍歷鏈表，一個(gè)快指針、一個(gè)慢指針，
     * 快指針每次向前移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)，
     * 當(dāng)快指針移動(dòng)到鏈表的末尾，慢指針?biāo)诘奈恢眉礊橹虚g結(jié)點(diǎn)所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，快指針已經(jīng)走到最后了
        //quickPoint.next.next == null是鏈表結(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，快指針已經(jīng)走到倒數(shù)第二個(gè)結(jié)點(diǎn)了
        //鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前一個(gè)
        while (quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    /**
     * 查詢指定下標(biāo)數(shù)據(jù)
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if(size<0 || index>size){//待查詢結(jié)點(diǎn)不存在
            return null;
        }
        if(index == 0){//查詢頭結(jié)點(diǎn)
            return head.data;
        }
        Node curNode =head;
        int i = 0;
        while (curNode != null) {
            if(i==index){//尋找到待查詢結(jié)點(diǎn)
                return  curNode.data;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
    }
    @Override
    public void addlast(T e) {
    }
    /**
     * 鏈表添加結(jié)點(diǎn):
     * 找到鏈表的末尾結(jié)點(diǎn)，把新添加的數(shù)據(jù)作為末尾結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)
     *
     * @param data
     */
    @Override
    public void add(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            end=head;//添加尾節(jié)點(diǎn)
            size++;
            return;
        }
        Node temp = end;
        temp.next = newNode;
        end=newNode;//修改尾節(jié)點(diǎn)
        size++;
    }
    /**
     * 鏈表刪除結(jié)點(diǎn):
     * 把要?jiǎng)h除結(jié)點(diǎn)的前結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后結(jié)點(diǎn)，即直接跳過(guò)待刪除結(jié)點(diǎn)
     * @param obj
     * @return
     */
    @Override
    public boolean remove(T obj) {
        if (head.data.equals(obj)) {//刪除頭結(jié)點(diǎn)
            head = head.next;
            size=0;
            return true;
        }
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (curNode.data.equals(obj)) {//尋找到待刪除結(jié)點(diǎn)
                preNode.next = curNode.next;//待刪除結(jié)點(diǎn)的前結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后結(jié)點(diǎn)
                size--;
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            preNode = preNode.next;
            curNode = curNode.next;
        }
        return  false;
    }
    @Override
    public boolean remove(int index) {
        if(size<0 || index>size){//待刪除結(jié)點(diǎn)不存在
            return false;
        }
        if(index == 0){//刪除頭結(jié)點(diǎn)
            head = head.next;
            return true;
        }
        Node preNode = head;
        Node curNode =head.next;
        int i =1; //從第2個(gè)值開(kāi)始
        while(preNode.next != null){
            if(i==index){//尋找到待刪除結(jié)點(diǎn)
                preNode.next= curNode.next;//待刪除結(jié)點(diǎn)的前結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后結(jié)點(diǎn)
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            preNode=curNode;
            curNode = curNode.next;
            i++;
        }
        return false;
    }
    @Override
    public boolean removeFirst() {
        return false;
    }
    @Override
    public boolean removeLast() {
        return false;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                OneWayLinked.this.remove(data);
            }
        };
    }
}

單向環(huán)形鏈表

它和單鏈表的區(qū)別在于結(jié)尾點(diǎn)的指針域不是指向null，而是指向頭結(jié)點(diǎn)，形成首尾相連的環(huán)。這種首尾相連的單鏈表稱為單向循環(huán)鏈表。循環(huán)鏈表可以從任意一個(gè)結(jié)點(diǎn)出發(fā)，訪問(wèn)到鏈表中的全部結(jié)點(diǎn)。

在這里插入圖片描述


單向循環(huán)鏈表的查找、刪除和修改操作與單鏈表一致(這里不在贅述，可參考前面的內(nèi)容)，插入操作和單鏈表有所不同，單向循環(huán)鏈表需要維持環(huán)狀結(jié)構(gòu)。判斷單鏈表為空的條件是head.next == null，而判斷單向循環(huán)鏈表為空的條件為head.next == head。

package com.lineardatastructure.linked;
import java.util.Iterator;
/**
 * @param <T>
 * @author huanmin
 */
// 單向循環(huán)鏈表
public class OneLoopWayLinked<T> extends LinkedAbs<T> {
    @Override
    public void reserveLink() {
        Object[] ts = new Object[size];
        int i = size - 1;
        for (T t : this) {
            ts[i] = t;
            i--;
        }
        Node node = head;
        node.data = (T) ts[0];
        for (int i1 = 1; i1 < ts.length; i1++) {
            Node node1 = new Node((T) ts[i1]);
            node.next = node1;
            node = node1;
            end= node1;
        }
        //調(diào)整位置
        end.next=head;
    }
    /**
     * 尋找單鏈表的中間結(jié)點(diǎn)：
     * 方法一、先求出鏈表的長(zhǎng)度，再遍歷1/2鏈表長(zhǎng)度，尋找出鏈表的中間結(jié)點(diǎn)
     * 方法二、：
     * 用兩個(gè)指針遍歷鏈表，一個(gè)快指針、一個(gè)慢指針，
     * 快指針每次向前移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)，
     * 當(dāng)快指針移動(dòng)到鏈表的末尾，慢指針?biāo)诘奈恢眉礊橹虚g結(jié)點(diǎn)所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，快指針已經(jīng)走到最后了
        //quickPoint.next.next == null是鏈表結(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，快指針已經(jīng)走到倒數(shù)第二個(gè)結(jié)點(diǎn)了
        //鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前一個(gè)
        while (quickPoint.next != head && quickPoint.next.next != head) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    /**
     * 查詢指定下標(biāo)數(shù)據(jù)
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (size < 0 || index > size) {//待查詢結(jié)點(diǎn)不存在
            return null;
        }
        if (index == 0) {//查詢頭結(jié)點(diǎn)
            return head.data;
        }
        Node curNode = head.next;
        int i = 1;
        while (curNode != head) {
            if (i == index) {//尋找到待查詢結(jié)點(diǎn)
                return curNode.data;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
    }
    @Override
    public void addlast(T e) {
    }
    /**
     * 鏈表添加結(jié)點(diǎn):
     * 找到鏈表的末尾結(jié)點(diǎn)，把新添加的數(shù)據(jù)作為末尾結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)
     *
     * @param data
     */
    @Override
    public void add(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head; //環(huán)型
            end = head;//添加尾節(jié)點(diǎn)
            size++;
            return;
        }
        Node temp = end;
        //一直遍歷到最后
        temp.next = newNode;
        newNode.next = head;//環(huán)型
        end = newNode;//修改尾節(jié)點(diǎn)
        size++;
    }
    /**
     * 鏈表刪除結(jié)點(diǎn):
     * 把要?jiǎng)h除結(jié)點(diǎn)的前結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后結(jié)點(diǎn)，即直接跳過(guò)待刪除結(jié)點(diǎn)
     *
     * @param obj
     * @return
     */
    @Override
    public boolean remove(T obj) {
        if (head.data.equals(obj)) {//刪除頭結(jié)點(diǎn)
            head = head.next;
            end.next=head;//調(diào)整環(huán)
            size--;
            return true;
        }
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != head) {
            if (curNode.data.equals(obj)) {//尋找到待刪除結(jié)點(diǎn)
                preNode.next = curNode.next;//待刪除結(jié)點(diǎn)的前結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后結(jié)點(diǎn)
                size--;
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            preNode = preNode.next;
            curNode = curNode.next;
        }
        return false;
    }
    @Override
    public boolean remove(int index) {
        if (size < 0 || index > size) {//待刪除結(jié)點(diǎn)不存在
            return false;
        }
        if (index == 0) {//刪除頭結(jié)點(diǎn)
            head = head.next;
            end.next=head;//調(diào)整環(huán)
            size--;
            return true;
        }
        Node preNode = head;
        Node curNode = head.next;
        int i = 1; //從第2個(gè)值開(kāi)始
        while (preNode.next != head) {
            if (i == index) {//尋找到待刪除結(jié)點(diǎn)
                preNode.next = curNode.next;//待刪除結(jié)點(diǎn)的前結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后結(jié)點(diǎn)
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }
        size--;
        return false;
    }
    @Override
    public boolean removeFirst() {
        return false;
    }
    @Override
    public boolean removeLast() {
        return false;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null&&cursor.next != head) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                if (cursor != null) {
                    data = cursor.data;
                    cursor = null;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                OneLoopWayLinked.this.remove(data);
            }
        };
    }
}

實(shí)現(xiàn)雙向鏈表

在這里插入圖片描述

package com.lineardatastructure.linked;
import java.util.Iterator;
/**
 * @author huanmin
 * @param <T>
 */
public class BothwayLinked<T> extends LinkedAbs<T> {
    /**
     *  查詢指定下標(biāo)數(shù)據(jù)
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (size < 0 || index > size) {//待查詢結(jié)點(diǎn)不存在
            return null;
        }
        if (index == 0) {//查詢頭結(jié)點(diǎn)
            return head.data;
        }
        Node curNode = head;
        int i = 0;
        while (curNode != null) {
            if (i == index) {//尋找到待查詢結(jié)點(diǎn)
                return curNode.data;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
        Node next = head;
        Node previous = new Node(e);
        previous.next = next;
        next.previous = previous;
        head=previous;
        size++;
    }
    @Override
    public void addlast(T e) {
        Node newNode = new Node(e);
        if (head == null) {
            head = newNode;
            size++;
            end=head;//添加尾節(jié)點(diǎn)
            return;
        }
        Node temp = end;
        temp.next = newNode;
        newNode.previous = temp;
        end=newNode;//修改尾節(jié)點(diǎn)
        size++;
    }
    @Override
    public void add(T e) {
        addlast(e);
    }
    @Override
    public boolean remove(T obj) {
        if (removeHead()) {
            return true;
        }
        Node curNode = head;
        while (curNode != null) {
            //尋找到待刪除結(jié)點(diǎn)
            if (curNode.data.equals(obj)) {
                //將刪除的節(jié)點(diǎn)后節(jié)點(diǎn),覆蓋刪除的節(jié)點(diǎn),然后將父節(jié)點(diǎn)指向被刪除元素的父節(jié)點(diǎn)
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //刪除的是最后節(jié)點(diǎn),那么就把他上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)刪除
                    previous.next=null;
                } else if (previous==null) {
                    //刪除的是頭節(jié)點(diǎn)的話,那么就不管父節(jié)點(diǎn)了
                    head=head.next;
                    head.previous=null;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)向后移
            curNode = curNode.next;
        }
        return false;
    }
    @Override
    public boolean remove(int index) {
        if (index<0 ||index >= size) {//待刪除結(jié)點(diǎn)不存在
            return false;
        }
        if (removeHead()) {
            return true;
        }
        Node curNode = head;
        int i = 0;
        while (curNode != null) {
            if (i == index) {//尋找到待刪除結(jié)點(diǎn)
                //將刪除的節(jié)點(diǎn)后節(jié)點(diǎn),覆蓋刪除的節(jié)點(diǎn),然后將父節(jié)點(diǎn)指向被刪除元素的父節(jié)點(diǎn)
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //刪除的是最后節(jié)點(diǎn),那么就把他上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)刪除
                    previous.next=null;
                } else if (previous==null) {
                    //刪除的是頭節(jié)點(diǎn)的話,那么就不管父節(jié)點(diǎn)了
                    head=head.next;
                    head.previous=null;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)向后移
            curNode = curNode.next;
            i++;
        }
        return false;
    }
    @Override
    public boolean removeFirst() {
        if (removeHead()) {
            return true;
        }
        Node node = head.next;
        node.previous = null;
        head = node;
        size--;
        return false;
    }
    @Override
    public boolean removeLast() {
        if (removeHead()) {
            return true;
        }
        //刪除尾節(jié)點(diǎn)
        end.previous.next=null;
        size--;
        return true;
    }
    //如果只有一個(gè)元素那么就將頭刪除
    public boolean removeHead() {
        if (head.next==null) {
            head=null;
            return true ;
        }
        return  false;
    }
    @Override
    public void reserveLink() {
        Object[] ts = new Object[size];
        int i = size - 1;
        for (T t : this) {
            ts[i] = t;
            i--;
        }
        Node node = head;
        node.data = (T) ts[0];
        for (int i1 = 1; i1 < ts.length; i1++) {
            Node node1 = new Node((T) ts[i1]);
            node.next = node1;
            node1.previous = node;
            node = node1;
        }
    }
    /**
     * 尋找單鏈表的中間結(jié)點(diǎn)：
     * 方法一、先求出鏈表的長(zhǎng)度，再遍歷1/2鏈表長(zhǎng)度，尋找出鏈表的中間結(jié)點(diǎn)
     * 方法二、：
     * 用兩個(gè)指針遍歷鏈表，一個(gè)快指針、一個(gè)慢指針，
     * 快指針每次向前移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)，
     * 當(dāng)快指針移動(dòng)到鏈表的末尾，慢指針?biāo)诘奈恢眉礊橹虚g結(jié)點(diǎn)所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，快指針已經(jīng)走到最后了
        //quickPoint.next.next == null是鏈表結(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，快指針已經(jīng)走到倒數(shù)第二個(gè)結(jié)點(diǎn)了
        //鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前一個(gè)
        while (quickPoint.next != null && quickPoint.next.next != null) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                BothwayLinked.this.remove(data);
            }
        };
    }
}

雙向循環(huán)鏈表

相比單鏈表，雙向循環(huán)鏈表是一個(gè)更加復(fù)雜的結(jié)構(gòu)。因?yàn)殡p向循環(huán)鏈表的節(jié)點(diǎn)不僅包含指向下一個(gè)節(jié)點(diǎn)的指針(next)，還包含指向前一個(gè)節(jié)點(diǎn)的指針(prev)。
在雙向循環(huán)鏈表中，可見(jiàn)的不只有頭指針head，還有尾節(jié)點(diǎn)end。這是和單鏈表的區(qū)別。
雙向循環(huán)鏈表的頭指針head的前一個(gè)節(jié)點(diǎn)指向end，尾節(jié)點(diǎn)end的后一個(gè)節(jié)點(diǎn)指向head。

在這里插入圖片描述

注意: 雙向循環(huán)鏈表,實(shí)現(xiàn)反查詢特別容易只需要反過(guò)來(lái)遍歷一遍就行

package com.lineardatastructure.linked;
import org.w3c.dom.Node;
import java.util.Iterator;
/**
 * @param <T>
 * @author huanmin
 */
public class BothwayLoopLinked<T> extends LinkedAbs<T> {
    @Override
    public void reserveLink() {
        Object[] ts = new Object[size];
        int i = size - 1;
        for (T t : this) {
            ts[i] = t;
            i--;
        }
        Node node = head;
        node.data = (T) ts[0];
        for (int i1 = 1; i1 < ts.length; i1++) {
            Node node1 = new Node((T) ts[i1]);
            node.next = node1;
            node1.previous = node;
            node = node1;
            end= node1;
        }
        //調(diào)整位置
        head.previous=end;
        end.next=head;
    }
    /**
     * 尋找單鏈表的中間結(jié)點(diǎn)：
     * 方法一、先求出鏈表的長(zhǎng)度，再遍歷1/2鏈表長(zhǎng)度，尋找出鏈表的中間結(jié)點(diǎn)
     * 方法二、：
     * 用兩個(gè)指針遍歷鏈表，一個(gè)快指針、一個(gè)慢指針，
     * 快指針每次向前移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)，
     * 當(dāng)快指針移動(dòng)到鏈表的末尾，慢指針?biāo)诘奈恢眉礊橹虚g結(jié)點(diǎn)所在的位置
     */
    @Override
    public T findMiddle() {
        Node slowPoint = head;
        Node quickPoint = head;
        //quickPoint.next == null是鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，快指針已經(jīng)走到最后了
        //quickPoint.next.next == null是鏈表結(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，快指針已經(jīng)走到倒數(shù)第二個(gè)結(jié)點(diǎn)了
        //鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前一個(gè)
        while (quickPoint.next != head && quickPoint.next.next != head) {
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint.data;
    }
    /**
     *  查詢指定下標(biāo)數(shù)據(jù)
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (size < 0 || index > size) {//待查詢結(jié)點(diǎn)不存在
            return null;
        }
        if (index == 0) {//查詢頭結(jié)點(diǎn)
            return head.data;
        }
        Node curNode = head.next;
        int i = 1;
        while ( curNode!= head) {
            if (i == index) {//尋找到待查詢結(jié)點(diǎn)
                return curNode.data;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            curNode = curNode.next;
            i++;
        }
        return null;
    }
    @Override
    public void addFirst(T e) {
        Node next = head;
        Node previous = new Node(e);
        previous.previous = head.previous;
        previous.next = next;
        next.previous = previous;
        head = previous;
        end.next=previous;//修改尾節(jié)點(diǎn)的指向
        size++;
    }
    @Override
    public void addlast(T e) {
        Node newNode = new Node(e);
        if (head == null) {
            head = newNode;
            head.previous=head;//環(huán)型
            head.next=head; //環(huán)型
            end=head;//添加尾節(jié)點(diǎn)
            size++;
            return;
        }
        Node temp = end;
        temp.next = newNode;
        newNode.previous = temp;
        newNode.next = head;//給為節(jié)點(diǎn)添加頭節(jié)點(diǎn)(環(huán)型)
        end=newNode;//修改尾節(jié)點(diǎn)
        size++;
    }
    @Override
    public void add(T e) {
        addlast(e);
    }
    @Override
    public boolean remove(T obj) {
        if (removeHead()) {
            return true;
        }
        //頭部刪除需要特殊處理
        if (obj == head.data) {
            Node previous = head.previous;
            head = head.next;
            head.previous = previous;
            end.next=head;
            size--;
            return true;
        }
        Node curNode = head.next;
        while (curNode != head) {
            //尋找到待刪除結(jié)點(diǎn)
            if (curNode.data.equals(obj)) {
                //將刪除的節(jié)點(diǎn)后節(jié)點(diǎn),覆蓋刪除的節(jié)點(diǎn),然后將父節(jié)點(diǎn)指向被刪除元素的父節(jié)點(diǎn)
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //刪除的是最后節(jié)點(diǎn),那么就把他上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)刪除
                    previous.next = null;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)向后移
            curNode = curNode.next;
        }
        return false;
    }
    @Override
    public boolean remove(int index) {
        if (removeHead()) {
            return true;
        }
        if (size < 0 || index >= size) {//待刪除結(jié)點(diǎn)不存在
            return false;
        }
        //頭部刪除需要特殊處理
        if (index==0) {
            Node previous = head.previous;
            head = head.next;
            head.previous = previous;
            size--;
            return true;
        }
        Node curNode = head.next;
        int i = 1;
        while (curNode != null) {
            if (i == index) {//尋找到待刪除結(jié)點(diǎn)
                //將刪除的節(jié)點(diǎn)后節(jié)點(diǎn),覆蓋刪除的節(jié)點(diǎn),然后將父節(jié)點(diǎn)指向被刪除元素的父節(jié)點(diǎn)
                Node previous = curNode.previous;
                Node next = curNode.next;
                if (next == null) {
                    //刪除的是最后節(jié)點(diǎn),那么就把他上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)給替換成頭節(jié)點(diǎn)
                    previous.next = head;
                } else {
                    next.previous = previous;
                    previous.next = next;
                }
                size--;
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)向后移
            curNode = curNode.next;
            i++;
        }
        return false;
    }
    @Override
    public boolean removeFirst() {
        head = head.next;
        head.previous = end; //環(huán)繞
        end.next=head; //環(huán)繞
        size--;
        return false;
    }
    @Override
    public boolean removeLast() {
        //將刪除結(jié)尾節(jié)點(diǎn)
        end.previous.next=head;
        size--;
        return true;
    }
    //如果只有一個(gè)元素那么就將頭刪除
    public boolean removeHead() {
        if (head.next==null) {
            head=null;
            return true ;
        }
        return  false;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node cursor = head;
            T data;
            @Override
            public boolean hasNext() {
                if (cursor != null&&cursor.next != head) {
                    data = cursor.data;
                    cursor = cursor.next;
                    return true;
                }
                if (cursor != null) {
                    data = cursor.data;
                    cursor = null;
                    return true;
                }
                return false;
            }
            @Override
            public T next() {
                return data;
            }
            @Override
            public void remove() {
                BothwayLoopLinked.this.remove(data);
            }
        };
    }
}

到此這篇關(guān)于Java實(shí)現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java鏈表數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • 淺談Java方法調(diào)用的優(yōu)先級(jí)問(wèn)題

    淺談Java方法調(diào)用的優(yōu)先級(jí)問(wèn)題

    這篇文章主要介紹了淺談Java方法調(diào)用的優(yōu)先級(jí)問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2020-10-10
  • myBatis組件教程之緩存的實(shí)現(xiàn)與使用

    myBatis組件教程之緩存的實(shí)現(xiàn)與使用

    這篇文章主要給大家介紹了關(guān)于myBatis組件教程之緩存的實(shí)現(xiàn)與使用的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-11-11
  • springboot項(xiàng)目配置swagger2示例詳解

    springboot項(xiàng)目配置swagger2示例詳解

    Swagger是一款RESTful接口的文檔在線自動(dòng)生成、功能測(cè)試功能框架。本文重點(diǎn)給大家介紹springboot項(xiàng)目配置swagger2示例代碼詳解，需要的朋友參考下吧
    2021-09-09
  • Java 如何獲取url地址文件流

    Java 如何獲取url地址文件流

    這篇文章主要介紹了Java 如何獲取url地址文件流，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
    2022-07-07
  • Java裝飾者模式的示例詳解

    Java裝飾者模式的示例詳解

    裝飾者模式：在不改變?cè)袑?duì)象的基礎(chǔ)之上，動(dòng)態(tài)的將功能附加到對(duì)象上，提供了繼承更有彈性的替代方案，也體現(xiàn)了開(kāi)閉原則。本文將通過(guò)示例詳細(xì)講解一下裝飾者模式，需要的可以參考一下
    2022-02-02
  • Java的SPI機(jī)制實(shí)例詳解

    Java的SPI機(jī)制實(shí)例詳解

    這篇文章主要介紹了Java的SPI機(jī)制實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • Java源碼重讀之ConcurrentHashMap詳解

    Java源碼重讀之ConcurrentHashMap詳解

    ConcurrentHashMap（CHM）是日常開(kāi)發(fā)中使用頻率非常高的一種數(shù)據(jù)結(jié)構(gòu)。本文將從源碼角度帶大家深入了解一下ConcurrentHashMap的使用，需要的可以收藏一下
    2023-05-05
  • Java壓縮之LZW算法字典壓縮與解壓講解

    Java壓縮之LZW算法字典壓縮與解壓講解

    今天小編就為大家分享一篇關(guān)于Java壓縮之LZW算法字典壓縮與解壓講解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧
    2019-02-02
  • java 使用正則表達(dá)式去除前后空格

    java 使用正則表達(dá)式去除前后空格

    這篇文章主要介紹了java 使用正則表達(dá)式去除前后空格，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2021-04-04
  • spring單元測(cè)試之@RunWith的使用詳解

    spring單元測(cè)試之@RunWith的使用詳解

    這篇文章主要介紹了spring單元測(cè)試之@RunWith的使用詳解,@RunWith 就是一個(gè)運(yùn)行器,@RunWith(JUnit4.class) 就是指用JUnit4來(lái)運(yùn)行,
    @RunWith(SpringJUnit4ClassRunner.class),讓測(cè)試運(yùn)行于Spring測(cè)試環(huán)境,需要的朋友可以參考下
    2023-12-12

最新評(píng)論