Java单链表2
用Java实现一个简单的单向链表,维护了 head 和 tail。
1、Java代码实现
package com.wangjia.datastruc;
/**
* 单向链表
* 基础功能: 增 删 取,
* 说明: 更新维护tail(代价),更快速支持某些操作e.g. addLast(好处).
*
* @author : wangjia
* @time : 2014-08-17 01:55
*/
public class OneWayLinkedList<T> {
private Node<T> head;
private Node<T> tail;
private int len;
public void add(T t) {
addToLast(t);
}
public void addToFirst(T t) {
Node<T> newNode = new Node<>(t);
newNode.next = head;
head = newNode;
len++;
}
public void addToLast(T t) {
Node<T> newNode = new Node<>(t);
if (head == null) {
tail = head = newNode;
len++;
return;
}
// 链接到尾部
tail.next = newNode;
//维护 tail 和 len
tail = newNode;
len++;
}
public void add(T t, int index) {
//长度为3,最多加到 index 4,最多比 len 多1
checkIndex(index - 1);
Node<T> newNode = new Node<>(t);
if (index == 1) {
addToFirst(t);
return;
}
Node<T> p = this.head;
//移动次数: index 2 = 0次, index 3 = 1次
for (int i = 1; i <= index - 2; i++) {
p = p.next;
}
newNode.next = p.next;
p.next = newNode;
len++;
}
public void rm(int index) {
checkIndex(index);
if (index == 1) {
head = head.next;
return;
}
Node<T> p = this.head;
//e.g. rm 2 -> 0 次, rm 3 -> 1次
for (int i = 1; i <= index - 2; i++) {
p = p.next;
}
//
//如果移除的是 tail ,tail需要新赋值
if (p.next.next == null) {
tail = p.next;
}
p.next = p.next.next;
len--;
}
public void rmLast() {
//如果长度为 0 或 1
if (len == 0 || len == 1) {
head.value = null;
head.next = null;
tail = head;
len = 0;
return;
}
Node<T> p = head;
for (int i = 1; i <= len; i++) {
if (p.next.next == null) {
p.next = null;
tail = p;
}
}
}
public T getFirstAndRm() {
if (len == 0) {
return null;
}
Node<T> p = this.head;
head = p.next;
T val = p.value;
p = null;
return val;
}
/**
* 假设链表第一个序号为 1
*/
public T get(int index) {
Node<T> p = head;
checkIndex(index);
if (index == len) {
return tail.value;
}
//e.g. index 1 -> 0 次移动, index 2 -> 1次移动
for (int i = 1; i <= index - 1; i++) {
//右移一次
p = p.next;
}
return p.value;
}
public T getFirst() {
if (head != null) {
return head.value;
}
return null;
}
public T getLast() {
if (head != null) {
return head.value;
}
return null;
}
/**
* @return len
*/
public int len() {
return 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();
}
private static class Node<T> {
Node<T> next;
T value;
public Node() {
}
public Node(Node<T> next, T value) {
this.next = next;
this.value = value;
}
public Node(T value) {
this(null, value);
}
}
private void checkIndex(int index) {
if (index > len) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + len;
}
}
2、简单测试
package com.wangjia.datastruc.test;
import com.wangjia.datastruc.OneWayLinkedList;
import org.junit.Assert;
import org.junit.Test;
public class OneWayLinkLinkTest {
/**
* 单链表测试
*/
@Test
public void testMyLinkList() {
OneWayLinkedList<String> list = new OneWayLinkedList<>();
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");
}
}