Java手写单向链表

1、什么是单向链表，有什么特点：

数据元素的存储对应的是不连续的存储空间,每个存储节点对应一个需要存储的数据元素。

每个结点是由数据域和指针域组成。元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻。

单向链表的节点就由data和next组成。data=数据；next=下一个节点；

2、单向链表缺点：

1.比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成所以相同空间内假设全存满的话顺序比链式存储更多)。

2.按照索引查找结点时链式存储要比顺序存储慢(每个节点地址不连续、无规律，导致按照索引查询效率低下。

3、单向链表优点：

1.插入、删除灵活(不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)。

2,有元素才会分配结点空间，不会有闲置的结点。有几个元素就有几个结点。不会存在闲置的空间。

4、带头节点的单链表

在使用单链表实现线性表的时候,为了使程序更加简洁,我们通常在单链表的最前面添加一个哑元结点，也称为头结点。

在头结点中不存储任何实质的数据对象，其next域指向线性表中0号元素所在的结点，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

5、单向链表的内存分配

我们一定要知道头节点的作用，才可以更好的理解单向链表的具体实现。比如我们执行这行代码：LinkedList linkedList = new LinkedList();这行代码在JVM里面具体是怎么分配的。

0x1012：单向链表的对象，它一开始就指向 0x2012这个内存地址。0x2012就是头节点，它是不存储数据的，只存储下一个节点的内存地址。头节点的下一个节点永远都是LinkedList集合的第一个元素。

我们往里面添加元素的内存变化：

通过上面的图，我们可以发现。单向链表的节点就是用来存储数据的地方，这个节点有两部分组成，一个地方是存储数据的，一个地方是存储下一个节点的。上一个节点的指针指向下一个节点的内存地址。通过这种数据结构来实现的单向链表功能。

6、接下来我们具体实现一个单向链表的代码

package com.zd.ArrayList;
//节点类
public class Node {

    public Object value;//存储数据的
    public Node next;//下一个节点

    public Node(Object value, Node next) {
        this.value = value;
        this.next = next;
    }

    public Node(Object value) {
        this.value = value;
    }

    public Node() {
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }
}

package com.zd.ArrayList;

public class MyLinkedList implements MyList{

    //链表的长度（不包括头节点）
    public int size;

    //初始化一个头节点
    public Node head = new Node();

    @Override
    public Node get(int index) {
        //健壮性判断下标的值
        if (index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("下标越界:"+index);
        }

        Node p = head;
        for (int i = 0; i <= index; i++){
            p = p.next;
        }
        return p;
    }

    @Override
    public void add(int index, Object o) {
        //新建一个元素指向头节点
        Node p = head;
        if(index > 0 ) {
          //如果传入的下标大于0的话，我们就获取上一个节点，如果等于0，默认指向头节点
            p = get(index - 1);
        }
        //创建一个新的节点
        Node newNode = new Node(o);
        //指定新节点的下一个节点
        newNode.next = p.next;
        //新节点之前的节点的下一个节点，指向新节点
        p.next = newNode;
        size++;
    }

    @Override
    public void add(Object o) {
        add(size,o);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (int i = 0; i < size; i++) {
            Node node = get(i);
            builder.append(node.value+",");
        }
        if(size != 0){
            builder.deleteCharAt(builder.length() -1);
        }
        builder.append("]");
        return builder.toString();
    }
}
@Override
    public void delete(int index) {
        //健壮性判断下标的值
        if (index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException("下标越界:"+index);
        }

        Node p = head;
        if(index > 0 ) {
            p = get(index - 1);
        }

        Node curNode = p.next;
        p.next = p.next.next;
        curNode.next = null;
        size--;
    }