Java教程
Java小白翻身-手写LinkedList
我们的第一个小目标，是做一个链表结构。其实就是之前写的TuziLinkedList，只不过我们不仅仅要存储Customer，还要存储任意的其他对象。
- 1、复习
- 2、单向链表
- 3、什么是继承？
- 4、为什么要放Object？
首先，我们复习一下之前写的链表结构：
源代码如下：
package tool;
import entity.Customer;
import tool.CustNode;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class TuziLinkedList implements Iterator{
public CustNode firstNode; //第一个节点
public CustNode currentNode;//当前的节点
public CustNode nodeForEach; //用于遍历的节点，默认等于第一个节点
//新增的方法
public void add(Customer cst){
//将数据用节点类包装好，这样才能实现下一个数据的指向
CustNode data = new CustNode(cst);
//先判断是否是第一个节点
if(this.firstNode == null){
this.firstNode = data;
this.currentNode = data;
}else{
//不是第一个节点，就指向当前节点的下一个节点，即currentNode.next
this.currentNode.next = data;
//因为已经指向下一个了，所以当前节点也要移动过来
this.currentNode = data;
}
}
//展示所有节点
public void display(){
//第一步，肯定是展示第一个节点(this其实可以省略的)
if(firstNode != null){
System.out.println(firstNode.data.getName());
//然后循环，一直寻找next是否为空
CustNode node = firstNode.next;
while(node != null ){
String name = node.data.getName();
System.out.println(name);
//循环的最后，再指向下一个节点，继续下一轮
node = node.next;
}
}
}
@Override
public boolean hasNext() {
if(nodeForEach == null && firstNode != null) return true;
if(nodeForEach == null) return false;
return nodeForEach.next != null;
}
@Override
public Object next() {
if(nodeForEach == null && firstNode != null){
nodeForEach = firstNode;
return nodeForEach.data;
}
nodeForEach = nodeForEach.next;
return nodeForEach.data;
}
}
TuziLinkedList类的核心就是一个单链表，里面维护了CustNode节点，代码如下：
package tool;
import entity.Customer;
public class CustNode{
public Customer data;
public CustNode next;
public CustNode(Customer data){
this.data = data;
}
}
我们的TuziLinkedList还实现了Iterator接口，这个接口可以帮助我们遍历TuziLinkedList中的内容。
以上是单链表的一般结构，我们会发现，链表中的每一个元素是一个Object，什么是Object呢？Object是Java里面的一个类，它是所有类的父类。在Java中，所有的类都默认继承自Object。
继承就是子类继承父类的特征和行为，使得子类对象（实例）具有父类的实例域和方法，或子类从父类继承方法，使得子类具有父类相同的行为。
这些都是概念上的解释，最多也就面试的时候问问。不过随着现在Java的行情越来越**“卷”**，面试也很少问这么基础的东西了。
随着我们代码的深入，相信你会对继承非常熟练的。
因此，与其我现在一股脑儿给你背书，读概念，还不如在之后的章节中，你自己看看继承都用在了哪些地方，是怎么用的？
回到正题，为什么链表的元素要放Object呢？那是因为，所有的类都会直接，或间接继承自Object。Java里面有一个叫做多态的特性，就是父类引用可以指向子类对象。
比如，我有一个人类，和教师类。
class Person{
}
class Teacher extends Person {
}
Teacher类用extends关键字，继承了Person类，那么说明Teacher类是Person类的子类对吧？
那么，你可以直接new一个Teacher类的对象：
Teacher t = new Teacher();
还可以这样：
Person p = new Teacher();
这也是允许的，但是需要注意的是，父类引用（p）指向了子类对象new Teacher()，那么p就只能调用Person类中的属性和方法，不能调用子类的。除非你用强制转换，像这样：
Person p = new Teacher(); Teacher t = (Teacher) p;
因为p本来就是Teacher的实例，所以你强制转换是允许的，只要你觉得有必要，就强转吧。
说了这么多，现在相信你明白为什么要用Object了吧，因为Object是所有类的父类，所以你用Object可以接收任意类型的对象啊，就这么简单！
方法重写，重载
刚开始，我们不要考虑太多，就做单链表即可。这一节，我们会遇到方法重写和重载的问题。
- 1、数据模型改为Object
- 2、AbstractSequentialList
- 3、add方法报错了
- 4、什么是方法重写？
- 5、重写add方法
- 6、欣赏原生的add方法
为了让我们的链表可以海纳百川，就把Node换成Object型的。
创建一个新的工具包：
CustNode改为Node，就是通用节点的意思。
package com.tuzi.util;
public class Node{
public Object data;
public Node next;
public Node(Object data){
this.data = data;
}
}
然后是TuziLinkedList，改为LinkedList。
JDK中的LinkedList继承了AbstractSequentialList类，这是一个抽象类。
啥叫抽象类，就是有abstract关键字的类，这种类有点像接口，就是里面会有一些方法只有声明而没有实现。我们看下AbstractSequentialList，里面就有一些这样的方法，比如：
public abstract ListIterator<E> listIterator(int index);
这种方法就是抽象方法，在之前接口的章节中，我们已经见过它了。
为了学习的深度，我们虽然不需要做到跟Java中的LinkedList一模一样，但是从表面上，也可以去和它一个标准。就是说，Java中的LinkedList继承了AbstractSequentialList，我们的LinkedList也要去继承AbstractSequentialList。
public class LinkedList extends AbstractSequentialList implements Iterator{
}
因为继承了AbstractSequentialList，我们就不得不去实现它里面所有的抽象方法（和接口真的有点像）
所以，我们不得不实现listIterator方法（就是上面介绍的那个）
@Override
public ListIterator listIterator(int index) {
return null;
}
虽然这是标准，但是我们现在，甚至连这个玩意到底干啥的都不知道，那就先放着。
继承了AbstractSequentialList之后，add方法就报错了。这是怎么回事呢？
从提示来看，是void用错了。
原来，AbstractSequentialList还继承了AbstractList。
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
}
AbstractList里面有一个方法也叫做add。
public boolean add(E e) {
add(size(), e);
return true;
}
参数是E，是泛型，目测编译器是把这种的也看成方法重写了。我们看下报错：
意思就是冲突啦，这个被认为是方法重写。
继续之前的例子，我们快速学习一下这个知识点。
class Person{
public void eat(){
System.out.println("人在吃饭。。。");
}
}
class Teacher extends Person {
public void eat(){
System.out.println("老师在吃饭。。。");
}
}
父类和子类都有一个eat方法，且都没有参数（即参数列表相同），返回值也相同，这就叫做参数重写。
测试代码：
Person p = new Teacher(); Teacher t = (Teacher) p; t.eat();
运行结果：
老师在吃饭。。。
注意，方法重写的前提是：
1.方法名
2.参数列表
3.返回值
以上三者全部相同，唯有方法体不一样。这种的才叫方法重写。
除了方法重写，还有一种叫做方法重载，就是同一个方法名，参数列表不同的情况，比如：
class Teacher extends Person {
public void eat(){
System.out.println("老师在吃饭。。。");
}
public void eat(String food){
System.out.println("老师在吃" + food );
}
}
两个方法都叫做eat，但是第二个eat方法多了一个参数，就是方法重载。注意，方法重载和返回值没有半毛钱关系，这个概念经常会在笔试题里面考。比如，下面这样的写法就是错误的：
编译器认为你这是把一个相同的方法写了两遍，所以给你报错了，再强调一遍，这可不是方法重载哦！
那么，如何修改add方法，才可以不报错呢？
很简单，让它的返回值和AbstractList里面的add方法一致就可以了。
public boolean add(Object object){
//将数据用节点类包装好，这样才能实现下一个数据的指向
Node data = new Node(object);
//先判断是否是第一个节点
if(this.firstNode == null){
this.firstNode = data;
this.currentNode = data;
}else{
//不是第一个节点，就指向当前节点的下一个节点，即currentNode.next
this.currentNode.next = data;
//因为已经指向下一个了，所以当前节点也要移动过来
this.currentNode = data;
}
return true;
}
这样就变成方法重写了。
我们来看下AbstractList中的原生add方法是怎么写的：
public boolean add(E e) {
add(size(), e);
return true;
}
我们可以发现，add方法接收一个参数e，然后立刻又调用了另一个add方法。很明显，这是方法重载，因为他的参数列表不同，接收两个参数。其中第一个参数size()，是一个方法的调用，这边得到的肯定是size方法的返回值。我们盲猜这个方法的作用是获取当前链表的长度，意思就是add方法增加的数据，直接就拼接到链表的末尾了。
到底是大佬写的代码啊，想的就是全面，而我们写的add方法，就没考虑那么多，直接添加到末尾了。
其实不一定的，万一我们要添加到链表的中间位置呢，是不是完全有可能呢？
那么，我们再来欣赏一下这个重载的add方法吧：
额，直接抛异常了？
再看看size：
public abstract int size();
直接就是抽象方法，而且，在他的子类AbstractSequentialList中也没有实现这个size方法，那么只能由继承AbstractSequentialList的LinkedList去实现啦。
至于那个add方法，直接抛了异常，意思大概就是我们必须去重写它了。虽然在AbstractSequentialList中，重写了这个add，但是我们不用它，因为它的设计太复杂了，不适合我们新手学习。
重写size方法
先挑软柿子捏，size方法无非就是获取链表的长度，来，搞起！
- 1、size思路
- 2、代码
我们可以抄袭，哦不，借鉴 java.util 包里面LinkedList中size的做法，就是直接设置一个int属性，每次add的时候就+1，remove的时候就-1。
我去，这个transient关键字是啥哦？
解释：
java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
不过呢，现在我们很少用到java里面的序列化了，基本都是json传输，或者xml传输。对于一些敏感的属性，我们可以通过注解的方式过滤掉，所以这个知识点我们简单识记一下即可。
显示增加属性：
private int size = 0; //链表中的元素个数，初始化为0
然后是size方法
@Override
public int size() {
return this.size;
}
没错，就这么简单。
重载add方法，这个才是最通用的。
- 1、欣赏父类的add方法
- 2、是否超出范围
- 3、初版实现
- 4、测试
- 5、另一种遍历方式
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
原来，父类AbstractSequentialList并没有亏待咱，已经写好了这个重载的add方法。不过呢，它的实现比较复杂，而且是针对双向链表的。我们的LinkedList是单链表，就不整那么复杂了，但是，我们可以参考下大佬的写法。
@Override
public void add(int index, Object element) {
boolean isOutSize = checkIndex(index);
if(isOutSize){
throw new IndexOutOfBoundsException("Index: "+index + "已经超出范围了，目前最大容量为" + size());
}
}
/**
* 检查下标是否超限
* @param index
* @return
*/
private boolean checkIndex(int index) {
return index > size;
}
上面有个超纲的内容，就是异常抛出，IndexOutOfBoundsException是范围超出异常，你现在就理解成程序手动报错就行了。
测试一下，先生成size的get，set方法。
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
然后，原来的add方法加上size的自增代码：
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add("苹果");
list.add("梨子");
System.out.println(list.getSize());
}
没问题，但是当我们给第三个位置添加元素时：
list.add(3,"柚子");
就报错了，符合我们的预期。
@Override
public void add(int index, Object element) {
boolean isOutSize = checkIndex(index);
if(isOutSize){
throw new IndexOutOfBoundsException("Index: "+index + "已经超出范围了，目前最大容量为" + size());
}
int loop = 0;
Node node = firstNode; //从第一个元素开始
while(node != null) {
loop++;
if(loop == index){
//如果已经是最后一个，则直接拼接
if(loop == size()){
Node newNode = new Node(element);
node.next = newNode;
//跳出循环
break;
}
//1.先保存当前节点的next，防止断尾
Node temp = new Node(node.next != null ? node.next.data:null);
temp.next = node.next != null ? node.next.next : null;
//2.之前断掉的部分接在新节点后面
Node newNode = new Node(element);
newNode.next = temp;
//3.新的节点接在node后面
node.next = newNode;
//跳出循环
break;
}else{
node = node.next;
}
}
}
/**
* 检查下标是否超限
* @param index
* @return
*/
private boolean checkIndex(int index) {
return index > size || index <= 0;
}
我们先用display方法来做测试。
LinkedList list = new LinkedList();
list.add("苹果");
list.add("梨子");
list.add(1,"柚子");
list.display();
但是，如果我们用增强for循环，就会报错。
for (Object o : list) {
System.out.println(o);
}
咋就空指针了呢？
这边还不好调试，只能去看反编译的代码：
重点就是
Iterator var2 = list.iterator();
这行代码，点进去看：
public Iterator<E> iterator() {
return listIterator();
}
listIterator，好眼熟啊，我们好像重写了对不？
对哦，当时我们嫌麻烦，就写了一个假的实现，直接就返回null了，所以肯定报错啊，哈哈。
正好复习一下之前的知识点，我们再来new一个匿名实现类。
LinkedList list = new LinkedList();
list.add("苹果");
list.add("梨子");
list.add(2,"柚子");
list.forEachRemaining(new Consumer() {
@Override
public void accept(Object o) {
System.out.println(o);
}
});
逼格瞬间就高了。
假如知道了下标，就该拿到对应的元素
- 1、代码实现
//取出某一个元素
public Object get(int index){
if(checkIndex(index+1)){
return null;
}
int i = 0;
Object o = null;
while((o = this.next())!= null){
if(i++ == index){
nodeForEach = null;//重置index
return o;
}
}
nodeForEach = null;//重置index
return o;
}
思路：先判断一下下标是否超限，然后去遍历所有节点，如果找到了对应的index，直接把value返回即可。
注意，不管有没有取出元素后，都要重置nodeForEach，不然遍历的时候会出问题。
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
