• 文章
  • 在线工具

java实现单向链表数据结构代码

单向链表 数据结构
78
package com.nanxhs.structure;

import java.util.Objects;

/**
 *
 * 单向链表实现
 * @author 唐海斌
 * @version 1.0
 * @date 2021/5/20 11:16
 */
public class UnidirectionalLinkList<T> {
    /**
     * 表头, 只是标识作用,一个空元素的Node
     */
    private final Node head;
    /**
     * 表尾
     */
    private Node tail;
    /**
     * 链表长度
     */
    private int size;

    public UnidirectionalLinkList() {
        head = new Node(null);
    }

    /**
     * 加入表尾
     * @param element
     */
    public synchronized void add(T element) {
        Node node = new Node(element);
        if (tail == null) {
            head.next = node;
            tail = node;
        } else {
            Node oldTail = tail;
            tail = node;
            oldTail.next = node;
        }
        ++size;
    }

    /**
     * 加入表头
     * @param element
     */
    public synchronized void addFirst(T element) {
        Node firstNode = head.next;
        Node node = new Node(element);
        if (firstNode == null) {
            head.next = node;
            tail = node;
        } else {
            head.next = node;
            node.next = firstNode;
        }
        ++size;
    }

    /**
     * 从链表中移除
     * @param element
     */
    public synchronized boolean remove(T element) {
        Node node = head;
        Node prev;
        Node currNode;
        boolean status = false;
        while (node != null) {
            prev = node;
            currNode = node.next;
            if (currNode == null) {
                break;
            }
            if (Objects.equals(element, currNode.element)) {
                if (currNode.next == null) {
                    prev.next = null;
                    currNode.element = null;
                }else {
                    prev.next = currNode.next;
                }
                --size;
                node = prev.next;
                status = true;
            } else {
                node = currNode;
            }
        }
        return status;
    }

    /**
     * 删除指定下标的元素
     * @param index
     * @return
     */
    public synchronized boolean remove(int index) {
        if (index > size - 1) {
            throw new RuntimeException("超过链表长度,当前链表的长度为: " + size);
        }
        Node node = head;
        int i = 0;
        while (node != null) {
            Node currentNode = node.next;
            if (currentNode == null) {
                return false;
            }
            if (Objects.equals(i, index)) {
                node.next = currentNode.next;
                if (--size == 0) {
                    tail = null;
                }
                return true;
            }
            node = currentNode;
            ++i;
        }
        return false;
    }

    /**
     * 获取指定下标的元素
     * @param index
     * @return
     */
    public T get(int index) {
        if (index > size - 1) {
            throw new RuntimeException("超过链表长度,当前链表的长度为: " + size);
        }
        Node node = head;
        int i = 0;
        while (node != null) {
            Node currentNode = node.next;
            if (currentNode == null) {
                return null;
            }
            if (Objects.equals(i, index)) {
                return currentNode.element;
            }
            node = currentNode;
            ++i;
        }
        return null;
    }

    /**
     * 清空链表
     */
    public void clear() {
        for (int index = size; index > 0; --index) {
            remove(0);
        }
    }

    /**
     * 获取链表长度
     *
     * @return
     */
    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder dataStr = new StringBuilder();
        dataStr.append("[");
        Node node = head;
        while ((node = node.next) != null) {
            dataStr.append(node.element).append(", ");
        }
        return dataStr.append("]").toString();
    }

    class Node {
        /**
         * 下一个节点
         */
        private Node next;
        /**
         * 当前节点元素
         */
        private T element;

        public Node(T element) {
            this.element = element;
        }
    }
}
import com.nanxhs.structure.UnidirectionalLinkList;
import org.junit.Assert;
import org.junit.Test;

/**
 * @author 唐海斌
 * @version 1.0
 * @date 2021/5/20 13:35
 */
public class UnidirectionalLinkListTest {

    @Test
    public void test() {
        UnidirectionalLinkList<String> unidirectionalLinkList = new UnidirectionalLinkList<>();
        unidirectionalLinkList.add("小明");
        unidirectionalLinkList.add("张三");
        Assert.assertEquals("张三", unidirectionalLinkList.get(1));

        unidirectionalLinkList.addFirst("李四");
        Assert.assertEquals("李四", unidirectionalLinkList.get(0));

        unidirectionalLinkList.remove("张三");
        Assert.assertEquals("小明", unidirectionalLinkList.get(1));

        unidirectionalLinkList.remove(1);
        Assert.assertEquals("李四", unidirectionalLinkList.get(0));

        unidirectionalLinkList.clear();
        Assert.assertEquals(unidirectionalLinkList.getSize(), 0);
    }
}


评论
或者使用社交账号快捷登录