java 实现 单链表 demo

Java

2017-07-07

42

0

技术:java8

运行环境:IDEA 15.2 + jdk8 + windows 10

demo功能:java实现单链表简单操作

源代码

http://git.oschina.net/youlixishi/demo-world/blob/master/src/algorithm/binary-search/src/main/java/com/demoworld/JSingleLinkedList.java

public class JSingleLinkedList {
    public JSingleLinkedList() {
        this.length = 0;
        head = null;
        tail = null;
    }

    public JLinkedListStackNode head;
    public JLinkedListStackNode tail;
    public int length;

    public void add(int n) {
        JLinkedListStackNode tmpNode = new JLinkedListStackNode();
        tmpNode.value = n;
        tmpNode.next = null;

        if (this.length == 0 || head == null) {//添加第一个元素
            head = tmpNode;
            tail = head;
            this.length++;
            return;
        }
        if (head.next == null) {//添加第二个元素
            head.next = tmpNode;
            tail = head.next;
            this.length++;
            return;
        }
        tail.next = tmpNode;//添加第三个以及之后的元素, 添加完成后,记得重置尾巴指针
        tail = tail.next;
        this.length++;
    }

    public boolean remove(int n) {
        if (this.isEmpty()) {
            return true;
        }
        if (head.value == n) {
            head = head.next;
            return true;
        }
        return remove(n, head, head.next) != null;
    }

    private JLinkedListStackNode remove(int n, JLinkedListStackNode pre, JLinkedListStackNode current) {
        if (current == null) {
            return null;
        }
        if (current.value == n) {
            pre.next = current.next;
            return current;
        }
        return remove(n, current, current.next);
    }

    public boolean exist(int n) {
        if (isEmpty()) {//添加第一个元素
            return false;
        }
        JLinkedListStackNode node = _getByValue(n, this.head);
        return node != null;
    }

    private JLinkedListStackNode _getByValue(int n, JLinkedListStackNode node) {
        if (node == null) {
            return null;
        }
        if (node.value == n) {
            return node;
        }
        return _getByValue(n, node.next);
    }

    public boolean isEmpty() {
        return this.length == 0;
    }
}

测试类

public class JSingleLinkedListTest {
    @Test
    public void testAdd1() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);

        Assert.assertEquals(3, list.length);
    }

    @Test
    public void testExist1() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);


        Assert.assertEquals(true, list.exist(13));
    }

    @Test
    public void testExist2() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);

        Assert.assertEquals(false, list.exist(110));
    }

    @Test
    public void testRemove1() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);


        Assert.assertEquals(true, list.remove(10));
    }

    @Test
    public void testRemove2() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);

        ;
        Assert.assertEquals(false, list.remove(100));
    }

    @Test
    public void testRemove3() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);

        list.remove(10);

        Assert.assertEquals(false, list.exist(10));
    }

    @Test
    public void testRemove4() {
        JSingleLinkedList list = new JSingleLinkedList();
        list.add(10);
        list.add(11);
        list.add(13);

        list.remove(13);

        Assert.assertEquals(false, list.exist(13));
    }
}

欢迎添加微信,互相学习↑↑↑ -_-

发表评论

全部评论:0条

白老虎

programming is not only to solve problems, ways to think