很多初学者都对这个数据结构非常的头疼，今天我们来实现一下数据结构中的线性结构，首先我们需要了解数据结构和线性结构
数据结构：数据结构 = 逻辑结构 + 物理结构(顺序、链式、索引、散列)
逻辑结构：数据元素间抽象化的相互关系
物理结构：在计算机存储器中的存储形式
List,Set就是逻辑结构
ArrayList，LinkedList就是物理结构
线性结构：数据结构中的元素是相连的关系，
常见的线性结构：链表、线性表、队列、串等
今天我们来实现一手单向链表和双向链表：首先我们先定义逻辑结构：
这里我们就通过实现List接口下的一些抽象方法
首先我们需要了解单向链表是如何存储元素的：
单向链表：链表是以节点的形式进行存储元素的，而单向链表的每个节点对象有两个成员变量：元素+下一个节点的地址
所以不管是单向链表还是双项链表我们都需要先创建节点对象，当节点对象做出来了这个结构就完成的差不多了
节点对象的实现：首先我们来实现节点对象，而单向链表的节点：元素 + 下一个节点的地址
所以我们需要定义两个成员变量：item和next，item用来存储元素，next指向下一个节点对象
public class MySingleListadd(E element)：implements MyList { class Node { private E item;//存储元素 private Node next;//存储下一个节点对象 public Node(E item, Node next){ this.item = item; this.next = next; } }
节点类实现出来了，然后我们实现添加元素的方法，首先我们肯定要有一个指向头节点的节点对象，因为访问节点需要从头开始一个一个往下访问，或者从尾开始往前一个一个访问，
所以我们定义一个节点first指向单向链表的头
定义一个节点last指向单向链表的尾，
并且定义一个记录元素个数的size
定义了这些我们就可以开始添加元素了，添加元素第一步我们得先判断链表中是否有元素把，没有元素咱向哪添加呢？
第一步：判断链表是否为空，判断链表是否为空只要判断first是否为空就行了，因为没有了头哪来的身体呢
第二步：如果first为null，就说明此时还没有头，那么我们需要创建头节点并且传递元素+下一个节点对象的地址而下一个节点对象你知道是啥吗？咱也不知道啊，添加元素也是一个一个添加的，所以我们的下一个节点对象的地址为null，就说明他还没有下一个节点对象
那没有下一个节点对象，只有一个头节点对象，那么尾节点是不是也就是头节点
此时的内存图是这样的：
第三步：如果头节点不为null,那么就说明已经有节点了，那么我们直接创建节点对象并传递元素以及下一个节点对象的引用，单向链表存储元素时默认在尾节点添加元素，那么说的尾节点，节点对象last不就派上用场了吗，我们直接让last指向的节点对象的next指向新创建的节点对象，那么此时新创建的节点对象就是新的尾节点，我们让last再指向这新创建的节点对象
第四步：size++，最后我们在对元素的个数进行记录
package com.java; public class MySingleListsize()：implements MyList { //存放头节点 private Node first; //存放尾节点 private Node last; //记录元素个数 private int size; @Override public void add(E element) { //第一种方式 //创建节点 //如果没有头节点，先创建头节点 if(first == null){ first = new Node<>(element,null); //节点的挂接 last = first; } //有了头节点创建节点 else { Node next = new Node (element,null); this.last.next = next; //节点的挂接 this.last = next; } //记录元素个数 this.size++; }
size()方法非常简单，我们定义了成员变量size，而这个size就是为了记录元素的个数的，那么我们直接调用成员变量size就可获取到元素的个数了
@Override
public int size() {
return this.size;
}
get(int index)：
因为我们的节点对象只能指向下一个节点对象，如果我们想要找到头节点以后的节点对象，我们就需要通过头节点一直往后找
第一步：检查下标的合法性，如果下标不在0~size之间，就说明下标越界了，那么我们抛出下标越界异常
第二步：根据下标找到节点对象，因为单向链表是不连续的，但是元素与元素之间是通过引用的方式连着的就像这样：
所以找中间的节点对象需要通过头节点往后找，我们可以将寻找元素的代码提取出来，通过一个searchNode方法去实现寻找节点的功能，我们在searchNode方法中通过for循环一个个向后找，直到i = index时，返回此时的节点对象
@Override
public E get(int index) {
//对index进行校验
checkIndex(index);
//根据下标获取节点对象
Node ret = searchNode(index);
//返回节点的元素
return ret.item;
}
//对index进行检验
private void checkIndex(int index){
if(!(index >= 0 && index <= this.size))
throw new IndexOutOfBoundsException();
}
//寻找节点的方法
private Node searchNode(int index){
//对index进行校验
checkIndex(index);
Node node = this.first;
for (int i = 0; i < index; i++){
node = node.next;
}
return node;
}
remove(int index)：
第一步：声明了两个Node对象，我们对传入的下标进行检验
第二步：下标检验合法过后，判断删除的是否是头节点，如果是头节点，使node对象指向头节点，那我们要将头删除，那是不是要让成员变量first指向头节点的下一个节点。我们删除了头节点，那么头节点的下一个节点不就是新的头节点吗？
第三步：如果删除的不是头节点，那么就是另一种方法，我们先获取下标所对应元素的上一个节点，然后获取下标所对应的节点对象，将下标所对应节点的上一个节点的next指向下标所对应节点的下一个
原本是这样：
删除元素过后
然后我们删除了元素，就需要对元素的个数进行记录
最后返回被删除节点的元素
@Override
public E remove(int index) {
Node last = null;
Node node = null;
//对index进行检验
checkIndex(index);
//如果删除的是头节点
if(index == 0){
//为后期断掉此节点做准备
node = first;
//将头节点设置为原本头节点的下一个节点
first = first.next;
}
//如果删除的不是头节点
else
{
//找到下标所对应节点的前一个节点
last = searchNode(index-1);
//找到下标所对应的节点
node = searchNode(index);
//将下标所对应节点的前一个节点指向下标所对应节点的下一个节点
last.next = node.next;
}
//将被删除的节点断掉
node.next = null;
//记录元素个数
this.size--;
//返回被删除的元素
return node.item;
}
}
注意：单向链表的实现有一些问题，当我们删除元素时，删除节点，删除节点过后但是节点对下一个元素的引用没有置为空，就是说并没有删彻底，我们通过刚刚那个图来看：
我们删除节点过后并完全是这样的
而是这样的
双向链表：双向链表是通过节点与节点相连接所实现的，所以他与单向链表存储的形式差不多
只是双向链表节点与节点之间是相连接的，而单向链表是左边能访问右边，而右边不能访问左边
所以双向链表多了指向上一个节点的节点对象
public class MyDoubleListadd()：implements MyList{ private Node first; private Node last; private int size; class Node { Node prev;//记录前一个节点对象 E item;//记录元素 Node next;//记录下一个节点对象 Node(Node prev,E item,Node next){ this.prev = prev; this.item = item; this.next = next; } }
java的LinkedList容器就是双向链表的形式，它添加元素是默认从后面添加的，那我们也实现从后面添加元素
第一步：判断此时双向链表中是否有节点，而判断是否有节点可以通过这个双向链表有没有头来判断，如果first为null，那么此时链表就是空的，所以我们需要创建头节点，而头节点的上一个节点肯定是null的，不然咋叫头节点呢。
如果走了创建头节点的这一步就说明此时链表只有头节点一个节点，那么此时尾节点也就是头节点
第二步：如果链表不为空，那么就创建节点对象，并且让节点对象的上一个指向，现在的last，last就是此时链表的尾节点嘛，新的节点添加在链表的结尾那么说明这个节点称为新的尾节点，所以将last尾节点的next指向新的last尾节点，并且让成员变量last指向新的尾节点
第三步：记录元素的个数
@Override
public void add(Object element) {
//默认在尾部添加元素
addLast(element);
}
public void addFirst(Object element){
//如果此时没有节点
if(first == null){
//创建节点
first = new Node(null,element,null);
//节点连接
last = first;
}else{
//创建新的头节点
Node newFirst = new Node(null,element,first);
//节点连接
first.prev = newFirst;
//更改头部为新的头部
first = newFirst;
}
//记录元素个数
this.size++;
}
get(int index)：
现在我们来实现双向链表获取元素的方法，根据刚刚单向链表的获取元素的形式我们可以知道，单向链表是通过头一直往后找节点对象的，而双向链表可以通过头节点往后找或者从尾节点往前找，因为有节点对象有指向上一个节点对象的引用也有指向下一个节点对象的引用，所以当我们获取元素时，为了提高效率，我们可以判断需要寻找的节点离头节点或尾节点谁更近
这里主要讲一下isNear()方法:这个isNear()方法使用来判断我们要查找的对象离头节点近还是离尾节点近，而我们如何判断呢？我们可以通过size元素个数判断，当我们要找的元素小于等于size/2，那么就从头节点开始往后找，如果要找的元素大于size/2，就从尾节点开始往前找
而在Java中除法运算是比较消耗时间的，所以我们可以通过右移（>>）实现size / 2 的功能
@Override
public Object get(int index) {
Node node = null;
//检验下标是否合法
checkIndex(index);
//查找下标所对应的节点对象
node = searchNode(index);
//返回节点对象对应的元素
return node.item;
}
//检查下标是否合法
private void checkIndex(int index){
if(!(index>=0 && index> 1说明离头节点近
if(index <= (this.size >> 1)){
return first;
}
return last;
}
//实现寻找节点的方法
private Node searchNode(int index){
Node node = isNear(index);
if (node == first){
for (int i = 0; i < index; i++){
node = node.next;
}
}else if(node == last){
for (int i = size-1; i > index; i--){
node = node.prev;
}
}
return node;
}
size()：
获取元素的个数我们可以通过成员变量size获取
@Override
public int size() {
return this.size;
}
remove()：
删除元素需要有三种选择：
1、当删除元素的节点是头节点时
我们可以通过传入的下标判断要删除的元素是否为头节点，我们可以通过成员变量first获得头节点，而我们要删掉头节点，就说明头节点的下一个节点就是新的头节点，我们通过first.next获得头节点的下一个节点，并且将first指向新的头节点，并且断掉旧的头节点与链表的关系
2、当删除元素的节点是尾节点时
我们可以通过传入的下标判断要删除的元素是否为尾节点，我们可以通过成员变量last获得尾节点，而我们要删掉尾节点，就说明尾节点的上一个节点就是新的尾节点，我们通过last.prev获得尾节点的上一个节点，并且将last指向新的尾节点，并且断掉旧的尾节点与链表的关系
删除节点的方式就是和删除头节点的方式相反的
3、当删除元素的节点是中间节点时
当删除元素的节点是中间节点时，我们就需要将此节点的上一个节点与此节点的下一个节点进行相连接，就像这样：
最后不管是删除头节点、尾节点还是中间节点都会对元素进行一次记录
@Override
public Object remove(int index) {
//检验下标是否合法
checkIndex(index);
Node node = null;
//存放被删除节点对象的元素
E temp = null;
//如果删除的是头节点
if (index == 0){
//获取头节点的下一个节点
node = this.first.next;
//断掉头节点
this.first.next = null;
node.prev = null;
//存放被删除节点对象的元素
temp = first.item;
//将头节点的下一个节点设为头节点
first = node;
}
//如果删除的是尾节点
else if(index == size-1){
//获取尾节点的上一个节点
Node prev = last.prev;
//断掉尾节点
this.last.prev = null;
prev.next = null;
//方便返回被删除的元素
temp = last.item;
//将尾节点的上一个节点设置为新的尾节点
this.last = prev;
}
else
{
//获取下标所对应的节点对象
node = searchNode(index);
//获取下标所对应节点对象的前一个节点
Node prev = node.prev;
//获取下标所对应下一个节点对象
Node next = node.next;
//下标所对应前一个节点对象的next指向下标所对应下一个节点对象
prev.next = node.next;
//下标所对应下一个节点对象的prev指向下标所对应前一个节点对象
next.prev = prev;
//断掉当前下标节点对象
node.prev = null;
node.next = null;
//存放被删除节点对象的元素
temp = node.item;
}
size--;
return temp;
}
总结：单向链表对元素的访问需要从头部开始顺序读取
双向链表对元素的访问可以从头部也可以从尾部向前或向后读取
