链表(LinkedList)

public class LinkList<T> {
	//	记录头结点  
	private Node head;
	//	记录链表的长度
	private int N;
	//	结点类
	private class Node{
		//	存储数据
		T item;
		//	下一个结点
		Node next;
		public Node(T item, Node next) {
			this.item = item;
			this.next = next;
		}
		public Node() {};
	}
	public LinkList(){
		//	初始化头结点
		this.head = new Node();
		//	初始化元素个数
		this.N = 0;
	}
	//	清空链表
	public void clear() {
		this.head = null;
		this.N = 0;
	}
	//	获取链表的长度
	public int length() {
		return N;
	}
	//判断链表是否为空
	public boolean isEmpty() {
		return N == 0;
	}
	//获取指定位置i处的元素
	public T get(int i) {
		//	通过循环，从头结点开始往后查找
		Node node = head;
		for (int j = 0; j <= i; j++) {
			node = node.next;
		}
		return node.item;
	}
	//向链表中添加元素t
	public void insert(T t) {
		//找到当前最后一个结点
		Node last = head;
		while(last.next!=null)
			last = last.next;
		//创建新结点，保存元素t
		Node now = new Node(t,null);
		//让当前最后一个结点指向新结点
		last.next = now;
		//	让元素个数加一
		this.N++;
	}
	//向指定位置i处添加元素t
	public void insert(int i, T t) {
		Node pre = head;
		//找到i位置的前一个结点
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的结点
		Node cur = pre.next;
		//创建新结点，前一结点指向新结点，新结点指向原来i位置的结点
		Node now = new Node(t, cur);
		pre.next = now;
		//元素个数加一
		this.N++;
	}
	//删除指定位置i的元素，返回被删除的元素
	public T remove(int i) {
		//找到i位置前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			head = head.next;
		}
		//找到i位置的结点并保存
		Node cur = pre.next;
		//找到i位置下一个结点
		Node next = cur.next;
		//前一个结点指向下一个结点
		pre.next = next;
		//元素个数减一
		this.N--;
		return cur.item;
	}
	//查找元素i在链表中第一次出现的位置
	public int indexOf(T t) {
		//	从头开始依次查找每一个结点，取出item，和t比较，如果相同则找到了
		Node now = head;
		for (int i = 0; now.next!= null; i++) {
			now = now.next;
			if (now.item==t) {
				return i;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		//	创建单向链表对象
		LinkList<String> s1 = new LinkList<>();
 		//	测试插入
		s1.insert("姚明");
		s1.insert("科比");
		s1.insert("麦迪");
		s1.insert(1,"詹姆斯");
		for (int i = 0; i < s1.length(); i++) {
			System.out.println(s1.get(i));
		}
		System.out.println("-----------------------------");
		//	测试获取
		String getres = s1.get(1);
		System.out.println("获取索引1处的结果为：" + getres);
		//	测试删除
		String removeRes = s1.remove(0);
		System.out.println("删除的元素为："+removeRes+"\t删除后长度为："+s1.length());
		//测试返回元素第一次出现的索引
		System.out.println("麦迪第一次出现的索引为："+s1.indexOf("麦迪"));
		//	测试清空
		s1.clear();
		System.out.println("清空后链表中元素的个数为："+s1.length());
	}
}