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);
}
}
}