Java實作單向連結清單以及簡單功能

最近在看資料結構,看到了連結清單.

單向連結清單每個節點都有一個指向下一個元素的指針,最後一個節點的後繼節點為null表示連結清單的結束.

連結清單的周遊是從表頭開始,直到下個節點為空結束周遊.

Java實作單向連結清單以及簡單功能

放一個toString方法,示範下周遊.

@Override
public String toString() {
    if (headerNode == null) {
        return "[]";
    } else {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        sb.append(headerNode.element);
        ListNode<E> firstNode = headerNode;
        ListNode<E> iterator = firstNode.next;
        while (iterator != null) {
            sb.append(",").append(iterator.element);
            iterator = iterator.next;
        }
        return sb.append("]").toString();
    }
}

連結清單的插入分為三種情況

向表頭插入節點

将新節點的後繼節點指向原來的表頭,然後将表頭設定為新節點

Java實作單向連結清單以及簡單功能

/**
  * 向表頭增加元素
  * @param element 需要增加的元素
  */
 public void addFirst(E element) {
     ListNode<E> newFirstNode = new ListNode<>(element);
     newFirstNode.next = headerNode;
     headerNode = newFirstNode;
 }

向指定位置插入節點

将新節點的後繼節點更新為目标節點的後繼節點,然後将目标節點的後繼節點更新為新節點.

Java實作單向連結清單以及簡單功能

/**
 * 在指定元素後添加元素
 *
 * @param previousElement 先前的元素
 * @param newElement      插入的元素
 */
public void add(E previousElement, E newElement) {
    if (headerNode == null) {
        throw new RuntimeException("連結清單中沒有元素");
    }
    ListNode<E> firstNode = headerNode;
    ListNode<E> targetNode = null;
    if (firstNode.element.equals(previousElement)) {
        targetNode = firstNode;
    }
    ListNode<E> iterator = firstNode.next;
    while (iterator != null) {
        if (iterator.element.equals(previousElement)) {
            targetNode = iterator;
            break;
        }
        iterator = iterator.next;
    }
    if (targetNode == null) {
        throw new RuntimeException("連結清單中無法查找到指定元素所處的位置");
    } else {
        ListNode<E> newListNode = new ListNode<>(newElement);
        newListNode.next = targetNode.next;
        targetNode.next = newListNode;
    }
}

向表尾插入節點

将表尾節點的後繼節點更新為新節點,新節點的後繼節點為null.

/**
 * 向連結清單末尾添加元素
 *
 * @param element 需要添加的元素
 */
public void add(E element) {
    if (headerNode == null) {
        headerNode = new ListNode<>(element);
        return;
    }
    //擷取首節點
    ListNode<E> firstNode = headerNode;
    //周遊到尾節點,并将新節點的位址(指針)指派給next
    while (firstNode.next != null) {
        firstNode = firstNode.next;
    }
    firstNode.next = new ListNode<>(element);
}

删除也分三種情況

删除表頭

将表頭元素的後繼節點設定為新的表頭,然後将原表頭的後繼節點設定為null

Java實作單向連結清單以及簡單功能

删除中間的指定位置

将指定節點的前驅節點指向後繼節點.然後指定節點的後繼節點設定為null

Java實作單向連結清單以及簡單功能

删除表尾

将表尾的前驅節點的後繼節點設定為null即可.

Java實作單向連結清單以及簡單功能

/**
 * 移除連結清單中的某個元素
 *
 * @param element 需要移除的元素
 */
public boolean remove(E element) {
    if (headerNode == null) {
        throw new RuntimeException("連結清單中沒有元素");
    }
    ListNode<E> firstNode = headerNode;
    ListNode<E> iterator = firstNode.next;
    if (firstNode.element.equals(element)) {
        headerNode = iterator;
        firstNode.next = null;
        return true;
    }
    ListNode<E> preIterator = firstNode;
    while (iterator != null) {
        if (iterator.element.equals(element)) {
            preIterator.next = iterator.next;
            iterator.next = null;
            return true;
        }
        preIterator = iterator;
        iterator = iterator.next;
    }
    return false;
}

放個整體代碼.

package com.relic.linkedlist;


/**
 * 單向連結清單的簡單實作
 *
 * @author Relic
 */
public class MyLinkedList<E> {

    /**
     * 連結清單的表頭節點
     */
    private ListNode<E> headerNode;

    public MyLinkedList(E element) {
        headerNode = new ListNode<>(element);
        headerNode.next = null;
    }

    public MyLinkedList() {
        headerNode = null;
    }

    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add("test1");
        list.add("test2");
        list.add("test3");
        list.add("test2", "test4");
        list.addFirst("test0");
        System.out.println(list);
        System.out.println(list.indexOf(7));
        System.out.println(list.lastIndexOf(2));
        System.out.println(list.size());
        System.out.println(list.contains("test1"));
        System.out.println(list.remove("test3"));
        System.out.println(list);
    }

    /**
     * 向連結清單末尾添加元素
     *
     * @param element 需要添加的元素
     */
    public void add(E element) {
        if (headerNode == null) {
            headerNode = new ListNode<>(element);
            return;
        }
        //擷取首節點
        ListNode<E> firstNode = headerNode;
        //周遊到尾節點,并将新節點的位址(指針)指派給next
        while (firstNode.next != null) {
            firstNode = firstNode.next;
        }
        firstNode.next = new ListNode<>(element);
    }

    /**
     * 在指定元素後添加元素
     *
     * @param previousElement 先前的元素
     * @param newElement      插入的元素
     */
    public void add(E previousElement, E newElement) {
        if (headerNode == null) {
            throw new RuntimeException("連結清單中沒有元素");
        }
        ListNode<E> firstNode = headerNode;
        ListNode<E> targetNode = null;
        if (firstNode.element.equals(previousElement)) {
            targetNode = firstNode;
        }
        ListNode<E> iterator = firstNode.next;
        while (iterator != null) {
            if (iterator.element.equals(previousElement)) {
                targetNode = iterator;
                break;
            }
            iterator = iterator.next;
        }
        if (targetNode == null) {
            throw new RuntimeException("連結清單中無法查找到指定元素所處的位置");
        } else {
            ListNode<E> newListNode = new ListNode<>(newElement);
            newListNode.next = targetNode.next;
            targetNode.next = newListNode;
        }
    }

    /**
     * 向表頭增加元素
     *
     * @param element 需要增加的元素
     */
    public void addFirst(E element) {
        ListNode<E> newFirstNode = new ListNode<>(element);
        newFirstNode.next = headerNode;
        headerNode = newFirstNode;
    }

    /**
     * 移除連結清單中的某個元素
     *
     * @param element 需要移除的元素
     */
    public boolean remove(E element) {
        if (headerNode == null) {
            throw new RuntimeException("連結清單中沒有元素");
        }
        ListNode<E> firstNode = headerNode;
        ListNode<E> iterator = firstNode.next;
        if (firstNode.element.equals(element)) {
            headerNode = iterator;
            firstNode.next = null;
            return true;
        }
        ListNode<E> preIterator = firstNode;
        while (iterator != null) {
            if (iterator.element.equals(element)) {
                preIterator.next = iterator.next;
                iterator.next = null;
                return true;
            }
            preIterator = iterator;
            iterator = iterator.next;
        }
        return false;
    }

    /**
     * 傳回連結清單中是否包括某個元素
     *
     * @param element 查找的元素
     * @return 的布爾值
     */
    public boolean contains(E element) {
        ListNode<E> iterator = headerNode;
        do {
            if (iterator.element.equals(element)) {
                return true;
            }
            iterator = iterator.next;
        } while (iterator != null);
        return false;
    }

    /**
     * @return int 連結清單的長度
     */
    public int size() {
        int length = 0;
        ListNode<E> firstNode = headerNode;
        if (firstNode == null) {
            return 0;
        }
        ListNode<E> iterator = firstNode.next;
        while (iterator != null) {
            length++;
            iterator = iterator.next;
        }
        //加上首節點
        return length + 1;
    }

    /**
     * 根據角标傳回連結清單中的元素
     *
     * @param index 連結清單中的位置
     * @return 指定的元素
     */
    public E indexOf(int index) {
        ListNode<E> iterator = headerNode;
        for (int i = 1; i < index; i++) {
            if (iterator.next == null) {
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
            iterator = iterator.next;
        }
        return iterator.element;
    }

    /**
     * 傳回從末尾開始計數指定角标的元素
     *
     * @param index 從末尾開始的位置
     * @return 指定的元素
     */
    public E lastIndexOf(int index) {
        ListNode<E> pre = headerNode;
        ListNode<E> later = headerNode;
        //pre指針先移動index個長度
        for (int i = 1; i < index; i++) {
            //超對外連結表長度,
            if (pre.next == null) {
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
            pre = pre.next;
        }
        //同時移動兩個指針,直到pre指針到達尾端,此時later指針的位置即為所求位置
        while (pre.next != null) {
            pre = pre.next;
            later = later.next;
        }
        return later.element;
    }

    @Override
    public String toString() {
        if (headerNode == null) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            sb.append(headerNode.element);
            ListNode<E> firstNode = headerNode;
            ListNode<E> iterator = firstNode.next;
            while (iterator != null) {
                sb.append(",").append(iterator.element);
                iterator = iterator.next;
            }
            return sb.append("]").toString();
        }
    }

    static class ListNode<E> {
        private E element;
        private ListNode<E> next;

        ListNode(E element) {
            this.element = element;
            next = null;
        }

        ListNode() {
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+ size();
    }

}

Java實作單向連結清單以及簡單功能

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器