Java单链表

Java单链表

Java 版单链表实现,只维护 head。


一、Java代码实现

package com.wangjia.datastruc.linklist;

/**
 * 单向链表,内部值维护了head节点
 * 基础功能:
 * add - 支持任意index插入
 * rm  - 支持任意index插入
 * get - 任意 index 获取
 * 说明:
 * 1.链表第一个节点 index 为 1
 *
 * @author : wangjia
 * @date : 2014-06-15 13:55
 */
public class OneWayOnlyHeadLinkedList<T> {
    private static class Node<T> {
        Node<T> next;
        T value;

        Node(Node<T> next, T value) {
            this.next = next;
            this.value = value;
        }

        public Node(T value) {
            this(null, value);
        }
    }

    private Node<T> head;

    private int len;

    public T get(int index) {
        return getNode(index).value;
    }

    private Node<T> getNode(int index) {
        Node<T> p = this.head;
        checkIndex(index);
        //e.g. get 1 -> 移动 0 次,
        //e.g. get 2 -> 移动 1 次
        for (int i = 1; i <= index - 1; i++) {
            p = p.next;
        }
        return p;
    }

    public void add(T t) {
        add(t, len + 1);
    }

    public void addFirst(T t) {
        add(t, 1);
    }

    public void addLast(T t) {
        add(t, len + 1);
    }

    /**
     * 1.正常情况: 找到 index - 1,插入到后面
     * 2.特例:插入头结点
     */
    public void add(T t, int index) {
        //最大比 len 多 1
        checkIndex(index - 1);
        Node<T> newNode = new Node<>(t);
        //头节点
        if (index == 1) {
            newNode.next = head;
            head = newNode;
            len++;
            return;
        }
        //非头结点
        Node<T> p = getNode(index - 1);
        newNode.next = p.next;
        p.next = newNode;
        len++;
    }

    public void rmFirst() {
        rm(1);
    }

    public void rmLast() {
        rm(len);
    }

    public void rm(int index) {
        checkIndex(index);
        if (index == 1) {
            head = head.next;
            len--;
            return;
        }
        Node<T> p = getNode(index - 1);
        p.next = p.next.next;
        len--;
    }

    @Override
    public String toString() {
        if (head == null) {
            return "len:0";
        }
        StringBuilder s = new StringBuilder("len:");
        s.append(len).append("values:[ ");
        Node<T> p = this.head;
        for (int i = 1; i <= len; i++) {
            s.append(p.value).append(",");
            p = p.next;
        }
        s.append("]");
        return s.toString();
    }

    public int len() {
        return len;
    }

    private void checkIndex(int index) {
        if (index > len) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

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

二、简单测试

package com.wangjia.datastruc.test;

import com.wangjia.datastruc.linklist.OneWayOnlyHeadLinkedList;
import org.junit.Assert;
import org.junit.Test;

public class OneWayLinkOnlyHeadListTest {
    /**
     * 单链表测试
     */
    @Test
    public void testMyLinkListOnlyHead() {
        OneWayOnlyHeadLinkedList<String> list = new OneWayOnlyHeadLinkedList<>();
        Assert.assertEquals("len ", list.len(), 0);

        list.add("1");
        list.add("2");
        list.add("3");// 1 2 3
        Assert.assertEquals("len", list.len(), 3);
        Assert.assertEquals("value check 1", list.get(1), "1");
        Assert.assertEquals("value check 2", list.get(2), "2");
        Assert.assertEquals("value check 3", list.get(3), "3");

        list.add("5", 2); // 1 5 2 3
        Assert.assertEquals("value check add index ", list.get(1), "1");
        Assert.assertEquals("value check add index ", list.get(2), "5");
        Assert.assertEquals("value check add index ", list.get(3), "2");

        list.add("6", 1); // 6 1 5 2 3
        Assert.assertEquals("value check add index", list.get(1), "6");
        Assert.assertEquals("value check add index", list.get(2), "1");

        list.rm(1);  // 1 5 2 3
        Assert.assertEquals("after rm", list.get(1), "1");
        list.rm(3); // 1 5 3
        Assert.assertEquals("after rm", list.get(3), "3");

        try {
            list.rm(4); //error
        } catch (Exception e) {
            Assert.assertTrue(e instanceof  IndexOutOfBoundsException);
        }
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注