部分轉(zhuǎn)自http://www.itdecent.cn/p/6782f3d96471

單鏈表

什么是單鏈表

鏈表（Linked list）是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的引用(Pointer)。鏈表并不像數(shù)組那樣將數(shù)組存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存地址空間里，所以較之?dāng)?shù)組來(lái)說(shuō)這是一個(gè)優(yōu)勢(shì)。

單鏈表的特點(diǎn)

• 鏈表增刪元素的時(shí)間復(fù)雜度為O(1)，查找一個(gè)元素的時(shí)間復(fù)雜度為 O(n)；
• 單鏈表不用像數(shù)組那樣預(yù)先分配存儲(chǔ)空間的大小，避免了空間浪費(fèi)；
• 單鏈表不能進(jìn)行回溯操作，如：只知道鏈表的頭節(jié)點(diǎn)的時(shí)候無(wú)法快讀快速鏈表的倒數(shù)第幾個(gè)節(jié)點(diǎn)的值。

單鏈表的基本操作

獲取單鏈表的長(zhǎng)度

對(duì)于一個(gè)鏈表的長(zhǎng)度我們只能一次去遍歷鏈表的節(jié)點(diǎn)，直到找到某個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空的時(shí)候得到鏈表的總長(zhǎng)度：

public int getLength(Node head){
    if(head == null){
        return 0;
    }
    int len = 0;
    while(head != null){
        len++;
        head = head.next;
    }  
    return len;  
}

查詢指定索引的節(jié)點(diǎn)值或指定節(jié)點(diǎn)值的索引

查詢指定索引的節(jié)點(diǎn)值：

public int getValueOfIndex(Node head, int index) throws Exception {
    if (index < 0 || index >= getLength(head)) {
        throw new Exception("角標(biāo)越界！");
    }
    if (head == null) {
        throw new Exception("當(dāng)前鏈表為空！");
    }
    Node targetHead = head;
    while (targetHead.next != null && index > 0) {
        targetHead = targetHead.next;
        index--;
    }
    return targetHead.value;
}

查詢指定節(jié)點(diǎn)值的索引：

public int getNodeIndex(Node head, int value) {
    int index = -1;
    Node targetHead= head;
    while (targetHead!= null) {
        index++;
        if (targetHead.value == value) {
            return index;
        }
        targetHead= targetHead.next;
    }
    return -1;
}

添加一個(gè)元素

1、在已有鏈表頭部插入一個(gè)節(jié)點(diǎn)

public Node addAtHead(Node head, int value){
    Node newHead = new Node(value);
    newHead.next = head;
    return newHead;
}

2、在已有鏈表的尾部插入一個(gè)節(jié)點(diǎn)：

public void addAtTail(Node head, int value){
    Node node = new Node(value);
    Node targetHead= head;
    while( targetHead.next != null){
        targetHead= targetHead.next;
    }
    targetHead.next = node;   
}

3、在指定位置添加一個(gè)節(jié)點(diǎn)

public Node insertElement(Node head, int value, int index) throws Exception {
   //為了方便這里我們假設(shè)知道鏈表的長(zhǎng)度
   int length = getLength(head);
   if (index < 0 || index >= length) {
       throw new Exception("角標(biāo)越界！");
   }
   if (index == 0) {
       return addAtHead(head, value);
   } 
   else if (index == length - 1) {
       addAtTail(head, value);
   }
   else {
       Node pre = head;
       Node cur = head.next;
       while (pre != null && index > 1) {
           pre = pre.next;
           cur = cur.next;
           index--;
       }  //循環(huán)結(jié)束后 pre 保存的是索引的上一個(gè)節(jié)點(diǎn) 而 cur 保存的是索引值當(dāng)前的節(jié)點(diǎn)
       Node node = new Node(value);
       pre.next = node;
       node.next = cur;
   }
   return head;
}

在指定位置添加一個(gè)節(jié)點(diǎn)，首先我們應(yīng)該找到這個(gè)索引所在的節(jié)點(diǎn)的前一個(gè)，以及該節(jié)點(diǎn)，分別記錄這兩個(gè)節(jié)點(diǎn)，然后將索引所在節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn)，然后將新節(jié)點(diǎn)的 next 指針指向插入節(jié)點(diǎn)即可。與其他元素并沒(méi)有什么關(guān)系，所以單鏈表插入一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度為 O(1)。

而數(shù)組插入元素就不一樣了如果將一個(gè)元素插入數(shù)組的指定索引位置，那么該索引位置以后元素的索引位置(內(nèi)存地址)都將發(fā)生變化，所以一個(gè)數(shù)組的插入一個(gè)元素的時(shí)間復(fù)雜度為 O(n)；所以鏈表相對(duì)于數(shù)組插入的效率要高一些，刪除同理。

刪除一個(gè)元素

1、 刪除頭部節(jié)點(diǎn)

public Node deleteHead(Node head) throws Exception {
    if (head == null) {
        throw new Exception("當(dāng)前鏈表為空！");
    }
    return head.next;
}

2、 刪除尾節(jié)點(diǎn)：

public void deleteTail(Node head) throws Exception {
    if (head == null) {
        throw new Exception("當(dāng)前鏈表為空！");
    }
    Node targetHead = head;
    while (targetHead.next != null && targetHead.next.next != null) {
        targetHead= targetHead.next;
    }
    targetHead.next = null;
}

3、 刪除指定索引的節(jié)點(diǎn)：

public Node deleteElement(Node head, int index) throws Exception {
    int size = getLength(head);
    if (index < 0 || index >= size) {
        throw new Exception("角標(biāo)越界！");
    }
    if (index == 0) {
        return deleteHead(head);
    } 
    else if (index == size - 1) {
        deleteTail(head);
    }
    else {
        Node pre = head;
        while (pre.next != null && index > 1) {
            pre = pre.next;
            index--;
        }
        //循環(huán)結(jié)束后 pre 保存的是索引的上一個(gè)節(jié)點(diǎn) 將其指向索引的下一個(gè)元素
        if (pre.next != null) {
            pre.next = pre.next.next;
        }
    }
    return head;
}

由單鏈表的增加刪除可以看出，鏈表的想要對(duì)指定索引進(jìn)行操作（增加，刪除），的時(shí)候必須獲取該索引的前一個(gè)元素。