链表
什么是链表
链表是一种物理存储单元上非连续性，非顺序的存储结构，其物理结构不能直观的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
结点API设计：
表名 | Node |
|---|---|
构造方法 | Node(T t,Node next):创建Node对象 |
成员变量 | T item:存储数据Node next:指向下一个结点 |
单向链表API设计
表名 | LinkList |
|---|---|
构造方法 | LinkList():创建LinkList对象 |
成员方法 | 1. public void clear(): 空置线性表2.public boolean isEmpty():判断线性表是否为空，是返回true，否返回false3.public int length():获取线性表中元素的个数4.public T get(int i):读取并返回线性表中的i个元素的值5.public void insert(T t):往线性表中添加一个元素6.public void insert(int i,T t):在线性表的第i个元素之前插入一个值为t的数据元素7.public T remove(int i):删除并返回线性表中第i个数据元素8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1 |
成员内部类 | private class Node:结点类 |
成员变量 | 1.private Node head:记录首结点2.private int N:记录链表的长度 |
单向链表代码实现
代码语言：javascript复制public class LinkList implements Iterable{
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 LinkList(){
//初始化头结点
this.head = new Node(null,null);
//初始化元素个数
this.N = 0;
}
/**
* 清空线性表
*/
public void clear(){
this.head.next = null;
}
/**
* 判断线性表是否为空
*/
public boolean ifEmpty(){
return this.head.next==null;
}
/**
* 获取线性表中元素的个数
*/
public int length(){
return N;
}
/**
* 读取并返回线性表中第i个元素
*/
public T get(int i){
Node n = head.next;
for(int index=0;index iterator() {
return null;
}
public class LIterator implements Iterator{
private Node n;
public LIterator(){
this.n= head;
}
public boolean hasNext(){
return n.next!=null;
}
public Object next(){
n=n.next;
return n.item;
}
}
}
