數據結構02-鏈表

說明：由于該數據結構是由java并且是原生實現，所以與C有一些出入，不過原理是相同的

1.鏈表的定義

　　　　為了表示線性表元素a與a+1的邏輯關系，存儲數據時，除了存儲元素本身的信息之外，還存儲了直接后繼元素的位置信息。這兩部分組成的數據元素被稱為“結點”，一個結點分為兩部分，存放數據元素信息的部分被稱為數據域，

　　　　存放直接后繼元素位置的部分被稱為指針域。

　　　　單鏈表：結點指針域只存放直接后繼元素位置的鏈表，也叫單向鏈表。

　　　　雙鏈表：結點指針域同時存放前驅元素和后繼元素位置的鏈表，也叫雙向鏈表。

　　　　循環鏈表：一般的鏈表尾結點（最后一個結點）的指針域一般null，但是有的鏈表將最后一個節點的指針域指向頭結點，構成一個環，稱作循環鏈表。

　　　　頭結點： 一個鏈表的頭節點，就是指針域指向該鏈表的第一個結點的結點，一般用來唯一確定一個鏈表（也有的鏈表是不帶頭結點的，那時我們通過鏈表的第一個結點來確定鏈表），注意：頭結點的數據與是null

2.實現原理

　　　　鏈表的每一個結點包括兩部分，數據域和指針域，數據域用來存儲數據，指針域用來存儲后繼結點的位置。

class Link<T>{
    /**
    *用來存儲數據
    */
    T data;
    /**
    *用來存儲下一結點位置
     */
    Link next;
}

3.鏈表的基本操作

　　　　1.初始化 init() 創建一個鏈表

　　　　2.清空 clear() 清空一個鏈表

　　　　3.銷毀 destroy() 銷毀鏈表

　　　　4.在頭部插入一個結點 insertFront()

　　　　5.在尾部插入一個結點 insertBackend()

　　　　6.在任意位置插入一個結點 insertIndex()

　　　　7.刪除任意位置元素 delete()

　　　　8.查找元素 find()

　　　　9.獲取指定位置節點的值 get()

4.代碼實現

　　4.1鏈表代碼實現

package com.xiaobai.linelist;

/**
 * @Author: xiaobai
 * @Date: 2019/5/1 9:00
 * @email:
 * @address:
 * @desc 模擬單鏈表操作
 * @Version 1.0
 */
@SuppressWarnings("ALL")
public final class Link<T> {
    /**
     * data 是要存儲的數據
     */
    private T data;
    /**
     * next是下一結點的引用位置
     */
    public Link<T> next;

    /**
     * 初始化操作 構造方法返回一個空結點
     */
    public Link(){
        this.next = null;
        this.data = null;
    }

    /**
     * 構造一個新的鏈表結點
     * 新結點是沒有后繼結點的 所以直接null
     * @param data 數據
     */
    public Link(T data){
        this.data = data;
        this.next = null;
    }

    /**
     * 清空鏈表操作
     * @param link 要被清空的鏈表頭節點
     */
    public void clear(){
        //讓每一個結點的引用都為 null GC 自動回收
        Link<T> link = this;
        while(link.next!=null){
            Link curr = link.next;
            link.next = link.next.next;
            curr = null;
        }
        link = null;
    }

    /**
     * 銷毀鏈表 這里的銷毀和清空我認為沒有什么區別，所以直接調用
     * 如果大家認為有區別的話，可以與我交流
     * @param link 被銷毀的鏈表
     */
    public void destroy(){
        this.clear();
    }

    /**
     * 在鏈表的頭部插入一個結點（默認是帶頭結點的鏈表）
     * @param head 鏈表的頭節點
     * @param data 被插入的數據
     * @return 插入結果
     */
    public boolean insertFront(T data){
        //先構建一個新的結點
        Link<T> node = new Link<T>(data);
        try {
            //將結點插入到頭部 即 新節點后繼指向原來的第一個結點  頭節點后繼指向新節點
            node.next = this.next;
            this.next = node;
            return true;
        }catch (Exception e){
            e.printStackTrace();
            return false;
        }
    }

    /**
     * 在鏈表的尾部插入一個結點
     * @param head 鏈表頭節點
     * @param data 要插入的數據
     * @return 插入結果
     */
    public boolean insertBackend(T data){
        //先構建一個新的結點
        try {
            Link<T> node = new Link<T>(data);
            //然后找到鏈表的尾
            Link<T> point = this.next;
            while(point.next!=null){
                point = point.next;
            }
            //插入
            point.next = node;
            return true;
        } catch (Exception e) {
            e.printStackTrace();
            return false;
        }
    }

    /**
     * 在任意位置插入一個結點
     * @param head 要插入的鏈表
     * @param i  插入位置 從0開始
     * @param data 插入的數據
     * @return 插入結果
     */
    public boolean insertIndex(int i,T data){
        Link curr = this.next;
        //空鏈表 拒絕插入
        if(null == curr && i > 0){
            return false;
        }
        int count = 0;
        //找到被插入的位置（要找被插入位置前一個）
        while(count != i-1 && null != curr){
            curr = curr.next;
            count ++;
        }
        //如果循環提前結束 說明i值過大
        if(count != i-1){
            return false;
        }
        //開始插入節點
        Link<T> node = new Link<T>(data);
        node.next = curr.next;
        curr.next = node;
        return true;
    }

    /**
     * 刪除任意位置元素
     * @param i 被刪除的位置  從0 開始
     * @return 被刪除的元素 刪除失敗返回null
     */
    public T delete(int i){
        T del = null;
        int count = 0;
        Link<T> curr = this.next;
        //找到被刪除結點的前一個結點
        while (curr != null&& count < i-1){
            curr = curr.next;
            count++;
        }
        //如果不滿足條件 刪除失敗
        if(count!=i-1){
            return del;
        }
        //如果找到 執行刪除操作 （GC 自動釋放）
        del = curr.next.data;
        curr.next = curr.next.next;
        return del;
    }

    /**
     * 查找元素是否存在  可能需要重寫存儲對象的equals方法
     * @param data 被查找元素
     * @return 查找結果
     */
    public boolean find(T data){
        Link curr = this.next;
        while(curr != null){
            if(curr.data.equals(data)||curr.data ==data){
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    /**
     * 獲取指定位置的元素
     * @param i 位置
     * @return 獲取到的值 沒有返回null
     */
    public T get(int i) {
        T data = null;
        Link<T> curr = this.next;
        int count = 0;
        while(count!=i && curr!=null){
            curr = curr.next;
            count ++;
        }
        if(count == i && curr!= null){
            data = curr.data;
        }
        return data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder().append("HashCode = "+this.hashCode()).append(" {head -> ");
        Link<T> curr = this.next;
        while (curr!=null){
            sb.append(curr.data+" -> ");
            curr = curr.next;
        }
        sb.append(" null}");
        return sb.toString();
    }
}

?

　　4.2? 測試代碼及結果

/**
 * @Author: xiaobai
 * @Date: 2019/5/1 9:42
 * @email: 
 * @address:
 * @Version 1.0
 */
public class TestLink {
    public static void main(String[] args) {
        System.out.println("初始化鏈表");
        Link<Integer> link = new Link<>();
        System.out.println("當前鏈表: "+link);

        System.out.println("在前端插入一個元素 5");
        link.insertFront(5);
        System.out.println("當前鏈表: "+link);

        for(int i=1;i<=10;i++){
            link.insertBackend(i);
        }
        System.out.println("依次從后端繼續插入10個數后： "+link);

        link.insertIndex(3,100);
        //索引從0開始
        System.out.println("在第三個位置上插入100以后的鏈表 "+link);

        System.out.println("在第100個位置上插入0 "+link.insertIndex(100,0));

        System.out.println("刪除第三個位置上的元素"+link.delete(3));
        System.out.println(link);

        System.out.println("查找元素10的結果"+link.find(10));
        System.out.println("查找元素100的結果"+link.find(100));

        System.out.println("獲取第3個結點的值 "+link.get(3));
        System.out.println("獲取第999個結點的值 "+link.get(999));

        link.clear();
        System.out.println("執行清空操作后的鏈表： "+link);

        link.destroy();

    }
}

　　　　　　運行結果圖：

?