java 數據結構與演算法---鏈表

原理來自百度百科 

一、鏈表的定義

　　鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

鏈表與線性表的區別：

1、由於不必須按順序存儲，鏈表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多。
2、查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。
3、使用鏈表結構可以剋服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。

二、單向連表

　　單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始；鏈表是使用指針進行構造的列表；又稱為結點列表，因為鏈表是由一個個結點組裝起來的；其中每個結點都有指針成員變數指向列表中的下一個結點

package com.jalja.org.algorithm;

public class MyLink<E> {
    private Node<E> nowNode;//最近添加的Node
    private int size=0;//鏈表的個數
    
    //節點
    static class Node<E>{
        private E data;
        private Node<E> next;
        public Node(E e,Node<E> ne){
            this.data=e;
            this.next=ne;
        }
    }
    /**
     * 插入元素
     * @param e
     */
    public void insert(E e) {
        if(nowNode==null) {
            nowNode=new Node<E>(e,null); 
        }else {
            nowNode=new Node<E>(e,nowNode); 
        }
        size++;
    }
    /**
     * 按照指定位置插入元素
     * @param e
     * @param pos
     */
    public void insert(E e,int pos) {
        if(pos>size) {
            throw new RuntimeException("指定位置太大");
        }
        if(pos==0) {
            insert(e);
        }else {
            Node<E> now=nowNode;
            for(int i=0;i<pos-1;i++) {
                now=now.next;
            }
            Node<E> node=new Node<E>(e,now.next);
            now.next=node;
            size++;
        }
    }
    /**
     * 查找指定元素的節點
     * @param e
     * @return
     */
    public Node<E> find(E e){
        Node<E> now=nowNode;
        while(now!=null) {
            if(now.data.equals(e)) {
                break;
            }
            now=now.next;
        }
        
        return now;
    }
    /**
     * 刪除指定元素
     * @param e
     */
    public void delete(E e) {
        Node<E> now=nowNode;//將要刪除的Node
        Node<E> nowPrev=nowNode;//要刪除元素的前一個Node
        while(now!=null) {
            if(now.data.equals(e)) {
                break;
            }
            nowPrev=now;
            now=now.next;
        }
        if(now==null) {
            throw new NullPointerException("指定元素不存在");
        }
        if(now==nowPrev) {
            nowNode=now.next;
        }else {
            nowPrev.next=now.next;
            now.next=null;
        }
        size--;
    }
    public void desplayAll() {
        Node<E> now=nowNode;
        while(now!=null) {
            System.out.println(now.data);
            now=now.next;
        }
    }
    public static void main(String[] args) {
        MyLink<String> link=new MyLink<String>();
        link.insert("A");
        link.insert("B");
        link.insert("C");
        
        link.desplayAll();
        
        link.insert("D", 0);
        
        link.delete("F");
        System.out.println("===================");
        link.desplayAll();
    }
}

三、雙向鏈表

 　　雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向迴圈鏈表。