目录
四、鲁迅说：一个是关于head.next，另一个也是head.next
一、前言
链表是一个和数组不一样的存储方式。我们都知道数组的存储地址是连续的，这样就不能很好的利
用好内存空间，而链表就解决了这个问题，链表是一存储地址不连续的的存储结构，这样的好处
就是能节省空间。
二、链表的简介
链表是由一系列的结点构成的，链表的第一个元素为头结点，头结点的特点是；不存放具体的数
表示单链表的表头，比如要找一个结点就是从头结点一个一个往下找的。
每一个结点有一个类似于指针的next，用来指向下一个结点，和一个date区域用于存储数据
头结点不存放数据，最后一个结点不指向null。
三、单向链表的API设置
代码实现
结点类：链表的设置结点类少不了
//定义节点类(成员内部类) private class Node{ //存储数据 T item; //下一个节点 Node next; public Node(T item,Node next){ this.item=item; this.next=next; } }
成员变量和构造方法
//记录头节点 private Node head; //记录链表的长度 private int N; //构造方法用来初始化成员变量 public LinkList(){ this.head=new Node(null,null); this.N=0; }
清空链表，链表的长度，链表是否为空
//方法1：清空链表 public void clear(){ head.next=null;//将头结点的指向置空 this.N=0;//元素个数变为0 } //方法2：链表的长度 public int length(){ return N;//N就是链表长度 } //方法3：判断链表是否为空 public boolean isEmpty(){ return this.N==0;//只需判断N是否为0即可 }
获取指定位置处的元素
//方法4：获取指定位置处的元素 public T get(int i){ Node node=head.next;//node是下一个结点 if(node!=null){//有下一个结点 for(int index=0;index<i;index++){ node=node.next;//往下一个结点移动 } return node.item; } return null; }
插入元素t(在链表的最后以结点后插入元素)
//方法5：插入元素t(在链表的最后以结点后插入元素) public void insert(T t){ //创建一个结点 Node node=head; while(node.next!=null){//找到最后一个结点的前一个结点 node=node.next; } Node newLast=new Node(t, null); //之前的最后指向现在的最后结点 node.next=newLast; //元素个数加一 N++; }
在指定i处，添加元素t
//方法6：在指定i处，添加元素t public void insert(int i,T t){ //创建一个结点，从头结点开始 Node node =head; for(int index=0;index<i;index++){//找到i位置处的前一个元素 node=node.next; } //当前i位置的结点 Node oldNode=node.next; //创建结点t Node newNode=new Node(t, null); //此时node表示的还是前一个结点，所以只需要把前一个结点指向创建的新结点 node.next=newNode; //新结点指向原来i位置处的结点，即可完成连接 newNode.next=oldNode; //元素个数加一 N++; }
删除指定位置i处的元素并返回被删除的元素
//方法7：删除指定位置i处的元素并返回被删除的元素 public T remove(int i) { //创建一个结点，从头节点开始 Node node=head; //因为是从头结点开始的，所以下面循环会找到i位置的前一个结点 for(int index=0;index<i;index++){ node=node.next; } //i位置处的结点 Node iNode=node.next; //直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点 node.next=iNode.next;//或者也可以node.next=node.next.next; //元素减1 N--; return iNode.item; }
查找元素t在链表中第一次出现的位置
//方法8：查找元素t在链表中第一次出现的位置 public int indexOf(T t){ Node node=head; for(int index=0;node.next!=null;index++){ node=node.next; if(node.item.equals(t)){ return index; } } //找不到 return -1; }
提供一个遍历的方法，实现Iterable接口
public class LinkList<T> implements Iterable{}
//实现Iterable接口，重写iterator方法 @Override //因为要的接口对象(接口不能直接new)，所以我们必须创建一个对象去实现这个接口 public Iterator iterator() { return new LIterator() ; } public class LIterator implements Iterator{ //实现Iterator接口重写hasNext()和next()两个方法 private Node n; public LIterator(){ this.n=head;//从头结点开始 } @Override public boolean hasNext() {//是否有元素 return n.next!=null; } @Override public Object next() {//返回下一个元素 n=n.next; return n.item; } }
全部代码概览：
import java.util.Iterator; public class LinkList<T> implements Iterable{ //定义节点类 private class Node{ //存储数据 T item; //下一个节点 Node next; public Node(T item,Node next){ this.item=item; this.next=next; } } //记录头节点 private Node head; //记录链表的长度 private int N; //构造方法用来初始化成员变量 public LinkList(){ this.head=new Node(null,null); this.N=0; } //方法1：清空链表 public void clear(){ head.next=null;//将头结点的指向置空 this.N=0;//元素个数变为0 } //方法2：链表的长度 public int length(){ return N;//N就是链表长度 } //方法3：判断链表是否为空 public boolean isEmpty(){ return this.N==0;//只需判断N是否为0即可 } //方法4：获取指定位置处的元素 public T get(int i){ Node node=head.next;//node是下一个结点 if(node!=null){//有下一个结点 for(int index=0;index<i;index++){ node=node.next;//往下一个结点移动 } return node.item; } return null; } //方法5：插入元素t(在链表的最后以结点后插入元素) public void insert(T t){ //创建一个结点 Node node=head; while(node.next!=null){//找到最后一个结点的前一个结点 node=node.next; } Node newLast=new Node(t, null); //之前的最后指向现在的最后结点 node.next=newLast; //元素个数加一 N++; } //方法6：在指定i处，添加元素t public void insert(int i,T t){ //创建一个结点，从头结点开始 Node node =head; for(int index=0;index<i;index++){//找到i位置处的前一个元素 node=node.next; } //当前i位置的结点 Node oldNode=node.next; //创建结点t Node newNode=new Node(t, null); //此时node表示的还是前一个结点，所以只需要把前一个结点指向创建的新结点 node.next=newNode; //新结点指向原来i位置处的结点，即可完成连接 newNode.next=oldNode; //元素个数加一 N++; } //方法7：删除指定位置i处的元素并返回被删除的元素 public T remove(int i) { //创建一个结点，从头节点开始 Node node=head; //因为是从头结点开始的，所以下面循环会找到i位置的前一个结点 for(int index=0;index<i;index++){ node=node.next; } //i位置处的结点 Node iNode=node.next; //直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点 node.next=iNode.next;//或者也可以node.next=node.next.next; //元素减1 N--; return iNode.item; } //方法8：查找元素t在链表中第一次出现的位置 public int indexOf(T t){ Node node=head; for(int index=0;node.next!=null;index++){ node=node.next; if(node.item.equals(t)){ return index; } } //找不到 return -1; } //实现Iterable接口，重写iterator方法 @Override //因为要的接口对象(接口不能直接new)，所以我们必须创建一个对象去实现这个接口 public Iterator iterator() { return new LIterator() ; } public class LIterator implements Iterator{ //实现Iterator接口重写hasNext()和next()两个方法 private Node n; public LIterator(){ this.n=head;//从头结点开始 } @Override public boolean hasNext() {//是否有元素 return n.next!=null; } @Override public Object next() {//返回下一个元素 n=n.next; return n.item; } } }
测试类下：
public class LinkListText { public static void main(String[] args) { //创建链表对象 LinkList<String> list=new LinkList<String>(); list.insert("张三"); list.insert("李四"); list.insert("王五"); list.insert("李四"); System.out.println("链表为空吗："+list.isEmpty()); for(Object s:list){ System.out.println(s); } //元素个数 System.out.println("初始元素个数："+list.length()); System.out.println("----------------------"); //插入 list.insert(1,"赵六"); list.insert(2,"历七"); //元素个数 System.out.println("插入后元素个数:"+list.length()); //第一次出现的位置 System.out.println("张三第一次出现的位置:"+list.indexOf("张三")); System.out.println("----------------------"); for(Object s:list){ System.out.println(s); } //清除链表 list.clear(); System.out.println("清除后，链表为空吗："+list.isEmpty()); } }
运行效果图：
四、鲁迅说：一个是关于head.next，另一个也是head.next
有关于左右边的.next解读：
左边的.next表示的是指向，右边的.next表示的下一个元素。
一般来说在左边的是指向，在右边的是下一个元素。（这里.next前可以是任意非null结点）
head.next!=null一样的道理。
