单链表的形式实现列表（线性表）

1. 我们可以使用数组和链表来实现列表（线性表），下面使用Java语言来实现单链表

2. Java中是没有指针的，但是Java中有引用，所以我们可以使用引用来代表一个指针，指向的是一个地址，所以这里是跟C语言链表不用的一个点

① 首先我们先创建一个ListNode类，这个类代表着链表的一个节点，我们可以在这个类中封装一些属性，包括节点的数据和下一个节点的引用

public class ListNode<T>{
	T data;
	ListNode<T> pre;
	ListNode<T> next;
	public ListNode(T data){
		super();
		this.data = data;
	}
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public ListNode <T> getNext() {
		return next;
	}
	public void setNext(ListNode <T> next) {
		this.next = next;
	}
	public ListNode <T> getPre() {
		return pre;
	}
	public void setPre(ListNode <T> pre) {
		this.pre = pre;
	}
}

② 因为我们一般要使用增删改查的操作所以可以写一个接口，里面声明这些方法，接口的代码如下：

import java.util.Iterator;
//线性表(列表)的接口定义
public interface MyList<T> extends Iterator<T>{
	//增加一个元素
	void add(T element);
	//删除相同元素
	void delete1(T element);
	//根据索引删除元素
	void delete2(int index);
	//将指定索引的元素修改为指定元素
	void update(int index, T newElement);
	//查询:当前列表中是否有target这个元素
	boolean contains(T element);
	//查找element,如果没有返回-1
	int indexOf(Object element);
	//通过返回指定索引出的元素
	T at(int index);
}

③ 创建一个类SingleLinkedList来实现这个接口，下面是具体实现增删改查的方法，其中插入节点的方法类似于C语言中的尾插法，两者没有什么本质上的区别，只是表达的方式由于语言的差别不同而已

public class SingleLinkedList<T> implements MyList<T>{
	//单链表
	//指定一个头结点
	private ListNode<T> first;
	private ListNode<T> last;
	private int size = 0;
	@Override
	public void add(T element) {
		//对于链表来说新增一个元素是新增一个节点,还没有头结点的时候新增一个节点
		if(first == null){
			//注意对象的引用与对象的next之间的区别
			first = new ListNode(element);
			last = first;
		}else{
			last.next = new ListNode(element);
			last = last.next;
		}	
		size++;
	}

	@Override
	public void delete1(Object element){
		ListNode<T> p = first;
		ListNode<T> pre = null;
		//这里容易出现空指针的异常因为pre初始化的时候为空然后进入循环的时候就满足条件了所以会导致空指针的异常
		while(p != null){
			if(p.data.equals(element)){
				if(p == first){
					//直接头指针往下进行移动就可以了
					first = first.next;
				}else{
					pre.next = p.next;
				}	
				size--;
				break;
			}
			pre = p;
			p = p.next;
		}
	}

	@Override
	public void delete2(int index){
		if(index <0 || index >= size)return;
		//写数据结构特别要注意边界的问题
		//删除索引为index的元素
		//凡是涉及到索引的问题是要链表来进行处理都是比较麻烦的,使用数组的话就比较方便因为数组本身是带有索引的
		ListNode<T> p = first;
		ListNode<T> pre = null;
		//i表示的是指向的节点的索引
		int i = 0;
		while(p != null){
			if(i == index){
				if(p == first){
					//直接头指针往下进行移动就可以了
					first = first.next;
				}else{
					pre.next = p.next;
				}	
				size--;
				break;
			}
			pre = p;
			p = p.next;
			i++;
		}
	}

	@Override
	public void update(int index, Object newElement) {
		ListNode p = first;
		int i = 0;
		while(p != null){
			if(i == index){
				//更新数据
				p.data = newElement;
				break;
			}
			p = p.next;
			i++;
		}
	}

	@Override
	public boolean contains(Object element) {
		ListNode p = first;
		while(p != null){
			if(p.data.equals(element)){
				return true;
			}
			p = p.next;
		}
		return false;
	}

	@Override
	public int indexOf(Object element) {
		ListNode p = first;
		//i表示的是指向的节点的索引
		int i = 0;
		while(p != null){
			if(p.data.equals(element)){
				return i;
			}
			p = p.next;
			i++;
		}
		return -1;
	}

	@Override
	public T at(int index){
		if(index <0 || index >= size)return null;
		ListNode p = first;
		//i表示的是指向的节点的索引
		int i = 0;
		while(p != null){
			if(i == index){
				return (T) p.data;
			}
			p = p.next;
			i++;
		}
		return null;
	}
	
	//重写toString方法
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		ListNode p = first;
		while(p != null){
			sb.append(p.data);
			if(p.next != null){
				sb.append(" , ");
			}
			p = p.next;
		}
		sb.append("]");
		return sb.toString();
	}

	private ListNode now = first;
	@Override
	public boolean hasNext(){
		System.out.println(now);
		System.out.println(first);
		return now != null;
	}

	@Override
	public T next() {
		ListNode next = now;
		now = now.next;
		return (T) next.data;
	}
}

④ 写一个Junited的测试类来进行这些方法的测试

import org.junit.Before;
import org.junit.Test;
public class SingleLinkedListTest{
	//声明的时候可以限定类型
	SingleLinkedList<String> list = new SingleLinkedList<String>();
	@Test
	@Before //需要使用@Before注解
	public void add(){
		//测试add方法的时候不需要使用@Before注解
		list.add("A");
		list.add("B");
		list.add("C");
		list.add("D");
		list.add("E");
		System.out.println(list);
	}

	@Test
	public void delete(){
		//测试delete方法的时候需要使用@Before注解
		//list.delete("A");
		list.delete1("B");
		System.out.println(list);
	}
	
	@Test
	public void deleteByIndex(){
		//测试delete方法的时候需要使用@Before注解
		//list.delete("A");
		list.delete2(0);
		System.out.println(list);
		//一般是使用断言来进行测试
		//Assertions.assertThat(list.toString())).isEqualsTo("[B,C,D,E]");
	}
	
	@Test
	public void update(){
		list.update(0, "B");
		System.out.println(list);
	}
	
	@Test
	public void contains(){
		System.out.println(list.contains("1"));
		System.out.println(list.contains("A"));
	}
	
	@Test
	public void indexOf(){
		System.out.println(list.indexOf("A"));
		System.out.println(list.indexOf("B"));
		System.out.println(list.indexOf("x"));
	}
	
	@Test
	public void at(){
		System.out.println(list.at(0));
	}
	
	@Test
	public void iter(){
		System.out.println(list.hasNext());
		
		while(list.hasNext()){
			System.out.println(list.next());
		}
	}
}