java数据结构与算法：单链表 SinglyLinkedList

这篇具有很好参考价值的文章主要介绍了java数据结构与算法：单链表 SinglyLinkedList。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

单链表 SinglyLinkedList

创建实现类并实现方法

package com.lhs;

public class SinglyLinkedList<E> implements List<E>{

    // 头节点
    private Node<E> first;

    // 尾节点
    private Node<E> last;

    // 节点数量
    private int size;

    public static class Node<E> {
        E data;
        Node<E> next;
        Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    // 返回节点数量
    @Override
    public int size() {
        return size;
    }

    // 判断链表是否为空
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断链表中是否包含某个元素
    @Override
    public boolean contains(Object o) {
        if(o == null) {
            for(Node<E> node = first;node != null;node = node.next){
                if (node.data == null) {
                    return true;
                }
            }
            return false;
        }else{
            for(Node<E> node = first;node != null;node = node.next){
                if(o.equals(node.data)){
                    return true;
                }
            }
        }
        return  false;
    }

    // 向链表中添加元素
    @Override
    public boolean add(E e) {
        Node<E> l = last;
        Node<E> eNode = new Node<>(e, null);
        if(l != null){
            l.next = eNode;
        }else{
            first = eNode;
        }
        last = eNode;
        size++;
        return true;
    }

    // 获取链表中指定索引位置的元素
    @Override
    public E get(int index) {
        if(index >= size || index < 0){
            throw new IndexOutOfBoundsException(index + "is out of bounds");
        }
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;
    }

    // 设置链表中指定索引位置的元素
    @Override
    public E set(int index, E e) {
        if(index >= size || index < 0){
            throw new IndexOutOfBoundsException(index + "is out of bounds");
        }
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        E oldVal = node.data;
        node.data = e;
        return oldVal;
    }

    // 移除链表中指定索引位置的元素
    @Override
    public E remove(int index) {
        if(index >= size || index < 0){
            throw new IndexOutOfBoundsException(index + "is out of bounds");
        }
        Node<E> node = first;
        Node<E> before = null;
        E oldVal;
        if(index == 0){
            oldVal = first.data;
            first = first.next;
        }else{
            for (int i = 0; i < index; i++) {
                if(i == index - 1){
                    before = node;
                }
                node = node.next;
            }
            oldVal = node.data;
            before.next = node.next;
        }
        size--;
        return oldVal;
    }

    // 向链表中添加元素到头部
    @Override
    public void addFirst(E e) {
        Node<E> oldVal = first;
        Node<E> eNode = new Node<>(e, oldVal);
        first = eNode;
        size++;
    }

    // 向链表中添加元素到尾部
    @Override
    public void addLast(E e) {
        add(e);
    }

    // 从链表中移除头部元素
    @Override
    public E removeFirst() {
        return remove(0);
    }

    // 从链表中移除尾部元素
    @Override
    public E removeLast() {
        return remove(size);
    }
}

测试

package com.lhs;

import org.junit.Test;

import static junit.framework.TestCase.*;
import static org.junit.Assert.assertThrows;

/**
 * SinglyLinkedList Test
 * 
 * @since 1.0.0 2020年5月4日
 * @author <a href="https://waylau.com">Way Lau</a>
 */
public class SinglyLinkedListTest {

    @Test
    public void testSize() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       assertTrue(list.size() == 0);

       list.add("Java");
       assertTrue(list.size() == 1);
    }

    @Test
    public void testIsEmpty() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       assertTrue(list.isEmpty());

       list.add("Java");
       assertFalse(list.isEmpty());
    }

    @Test
    public void testContains() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.add("Java");
       list.add("C++");
       list.add("C");
       list.add("Python");
       list.add("TypeScript");

       // 判断存在
       assertTrue(list.contains("Java"));

       // 判断不存在
       assertFalse(list.contains("Java++"));
    }

    @Test
    public void testAdd() {
       // 实例化SinglyLinkedList
       List<Integer> list = new SinglyLinkedList<Integer>();
       list.add(1);
       list.add(2);
       list.add(3);
       list.add(4);
       list.add(5);

       assertFalse(list.isEmpty());
    }

    @Test
    public void testGet() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.add("Java");
       list.add("C++");
       list.add("C");

       // 判断存在
       assertEquals("C++", list.get(1));

       // 判断不存在
       int index = 6;
       Throwable excpetion = assertThrows(
             IndexOutOfBoundsException.class, () -> {
                list.get(index);// 抛异常
             });

       assertEquals(index + "is out of bounds",
             excpetion.getMessage());
    }

    @Test
    public void testSet() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.add("Java");
       list.add("C++");
       list.add("C");

       // 判断存在
       assertEquals("C", list.set(2, "Python"));

       // 判断不存在
       int index = 6;
       Throwable excpetion = assertThrows(
             IndexOutOfBoundsException.class, () -> {
                list.set(index, "Python");// 抛异常
             });

       assertEquals(index + "is out of bounds",
             excpetion.getMessage());
    }

    @Test
    public void testRemove() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.add("Java");
       list.add("C++");
       list.add("C");

       // 判断存在
       assertEquals("C", list.remove(2));

       assertEquals("Java", list.get(0));
       assertEquals("C++", list.get(1));

       // 判断不存在
       int index = 6;
       Throwable excpetion = assertThrows(
             IndexOutOfBoundsException.class, () -> {
                list.remove(index); // 抛异常
             });

       assertEquals(index + "is out of bounds",
             excpetion.getMessage());
    }

    @Test
    public void testAddFirst() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.addFirst("Java");
       list.addFirst("C++");
       list.addFirst("C");

       // 判断存在
       assertEquals("C", list.get(0));
       assertEquals("C++", list.get(1));
       assertEquals("Java", list.get(2));
    }

    @Test
    public void testAddLast() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.addLast("Java");
       list.addLast("C++");
       list.addLast("C");

       // 判断存在
       assertEquals("Java", list.get(0));
       assertEquals("C++", list.get(1));
       assertEquals("C", list.get(2));
    }

    @Test
    public void testRemoveFirst() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.add("Java");
       list.add("C++");
       list.add("C");

       // 判断存在
       assertEquals("Java", list.removeFirst());
       assertEquals("C++", list.removeFirst());
       assertEquals("C", list.removeFirst());
    }

    @Test
    public void testRemoveLast() {
       // 实例化SinglyLinkedList
       List<String> list = new SinglyLinkedList<String>();
       list.add("Java");
       list.add("C++");
       list.add("C");

       // 判断存在
       assertEquals("C", list.removeLast());
       assertEquals("C++", list.removeLast());
       assertEquals("Java", list.removeLast());
    }
}