linkedList的構建

linkedList是由一個一個的節點構成的。而每個節點只需要儲存要儲存的資料和下一個節點的引用即可。

linkedList本身需要一個head節點，所以我們的linkedList可以這樣構建：

public class LinkedList {    Node head; // head 節點    //Node表示的是Linked list中的節點，包含一個data資料和下一個節點的引用    class Node {        int data;        Node next;        //Node的建構函式        Node(int d) {            data = d;        }    }}

linkedList的操作

先看一下linkedList怎麼插入資料，插入資料有三種方式，頭部插入，尾部插入，中間插入。

頭部插入

先看一個頭部插入的例子：

頭部插入的邏輯是什麼呢？

新插入的節點作為head節點，然後將原來的head節點指向當前head節點的next引用即可。

    //插入到linkedList的頭部    public void push(int newData) {        //構建要插入的節點        Node newNode = new Node(newData);        //新節點的next指向現在的head節點        newNode.next = head;        //現有的head節點指向新的節點        head = newNode;    }

尾部插入

再看一下尾部插入的例子：

插入的邏輯是什麼呢？

找到最後一個節點，然後將最後一個節點的next指向新插入的節點。

//新節點插入到list最後面    public void append(int newData) {        //建立新節點        Node newNode = new Node(newData);        //如果list是空，則新節點作為head節點        if (head == null) {            head = newNode;            return;        }        newNode.next = null;        //找到最後一個節點        Node last = head;        while (last.next != null) {            last = last.next;        }        //插入        last.next = newNode;        return;    }

中間插入

再看一下中間插入的例子：

這個例子中，我們在第三個節點的位置插入了一個93。

插入邏輯就是先找到第二個節點，將第二個節點的next指向新節點，然後將新節點的next指向原先的第三個節點。

看下java程式碼如何實現：

//插入在第幾個元素之後    public void insertAfter(int index, int newData) {        Node prevNode = head;        for (int i = 1; i < index; i++) {            if (prevNode == null) {                System.out.println("輸入的index有誤，請重新輸入");                return;            }            prevNode = prevNode.next;        }        //建立新的節點        Node newNode = new Node(newData);        //新節點的next指向prevNode的下一個節點        newNode.next = prevNode.next;        //將新節點插入在prevNode之後        prevNode.next = newNode;    }

刪除節點

再看一下怎麼刪除某個位置的節點：

看下相應的java程式碼如下：

    //刪除特定位置的節點    void deleteNode(int index)    {        // 如果是空的，直接返回        if (head == null)            return;        // head節點        Node temp = head;        // 如果是刪除head節點        if (index == 1)        {            head = temp.next;            return;        }        // 找到要刪除節點的前一個節點        for (int i=1; temp!=null && i<index-1; i++)            temp = temp.next;        // 如果超出範圍        if (temp == null || temp.next == null)            return;        // temp->next 是要刪除的節點，刪除節點        Node next = temp.next.next;        temp.next = next;    }

本文的程式碼地址：

learn-algorithm

本文收錄於 http://www.flydean.com/algorithm-linked-list/