单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据域) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

头指针head和终端结点

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。

单链表的实现代码

项目目录结构

结构体 ListNode.java
接口类 MyList.java
实现类 SingleLinkedList.java

基本的结构体

ListNode.java:

package day01线性表;
/*单链表的实现*/
public class ListNode {
    private Object data;//数据域
    private Object next;//指针域

    public ListNode(Object data) {
        this.data = data;
    }

	// getter 和 setter 方法，对应着c语言中的结构体指针指向
	// 也可以修改 data 和 next 两个成员变量的访问控制权限 ，直接通过 对象.成员变量来做
    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Object getNext() {
        return next;
    }

    public void setNext(Object next) {
        this.next = next;
    }
}

接口中的抽象方法

MyList.java:

package day01线性表;

public interface MyList {
    /**
     * 添加元素
     * @param element
     */
    void add(Object element);

    /**
     * 在指定位置插入元素
     * @param target
     * @param element
     */
    void add(int target,Object element);

    /**
     * 根据元素的值来删除
     * @param element
     */
    void delete(Object element);

    /**
     * 根据索引来删除元素
     * @param index
     */
    void delete(int index);

    /**
     * 根据指定的target索引位置来更新元素
     * @param traget
     * @param element
     */
    void update(int traget,Object element);

    /**
     * 返回某一元素第一次在线性表中出现的位置
     * @param element
     * @return
     */
    int indexOf(Object element);

    /**
     * 返回在指定target位置的元素
     * @param target
     * @return
     */
    Object elementAt(int target);

    /**
     * 取指定索引位置元素的前驱元素
     * @param index
     * @return
     */
    Object elementPrior(int index);

    /**
     * 取指定索引位置元素的后继元素
     * @param index
     * @return
     */
    Object elementNext(int index);

    /**
     * 是否包含某一元素
     * @param element
     * @return
     */
    boolean contains(Object element);
}

实现类

SingleLinkedList.java:

package day01线性表;

import java.util.LinkedList;

public class SingleLinkedList implements MyList{
    private ListNode head;//头节点
    private ListNode last;//尾节点
    private int size;//记录节点个数
    @Override
    public void add(Object element) {
        if(head==null){
            //一开始，头尾结点指向同一处
            head = new ListNode(element);
            last = head;
        }else{
            //尾插法
            last.setNext(new ListNode(element));
            //将 last 移动到自己的后继元素上
            last = (ListNode) last.getNext();
        }
        size++;
    }

    @Override
    public void add(int target, Object element) {
        //这里这个指定位置插入，对于单链表意义不大，所以就忽略不写了
    }

    @Override
    public void delete(Object element) {
        //同样还是先记录头结点
        ListNode p = head;
        ListNode pre = null;//前驱节点一开始为空，方便后来的删除
        // 因为单链表中的删除，就是将要删除的节点的前驱，直接指向要删除节点的后继节点
        while (p!=null){
            if(p.getData().equals(element)){
                //如果删除的是头节点的值，那么就直接修改head指向即可
                if(p==head){
                    head = (ListNode) head.getNext();
                    size--;
                    return;
                }else {
                    // 删除节点的前驱指向删除节点的后继
                    pre.setNext(p.getNext());
                    size--;
                    return;
                }
            }
            //没找到就一直往后面移动 pre 和 p
            pre = p;
            p = (ListNode) p.getNext();
        }
        //如果就是整个链表中都没找到则打印输出
        System.out.println("当前链表中中不存在值为"+element.toString()+"的元素，无法删除!");
    }

    @Override
    public void delete(int index) {
        //index越界判断
        if(index<0||index>=size){
            System.out.println("要访问的索引已经越界!无法进行删除");
            return;
        }
        int i = 0;//一开始头节点的索引为0
        ListNode p = head;
        ListNode pre = null;//头节点的前驱节点为空
        while (p!=null){
            if(i==index){
                //如果删除的是头节点的值，那么就直接修改head指向即可
                if(p==head){
                    head = (ListNode) head.getNext();
                    size--;
                    return;
                }else {
                    // 删除节点的前驱指向删除节点的后继
                    pre.setNext(p.getNext());
                    size--;
                    return;
                }
            }
            //没找到就一直往后面移动 pre 和 p
            pre = p;
            p = (ListNode) p.getNext();
            i++;
        }
    }

    @Override
    public void update(int traget, Object element) {
        //index越界判断
        if(traget<0||traget>=size){
            System.out.println("要访问的索引已经越界!无法进行修改");
            return;
        }
        int i = 0;//一开始头节点的索引为0
        ListNode p = head;
        while (p!=null){
            if(i==traget){
                p.setData(element);
                return;
            }
            //没找到就一直往后面移动 p
            p = (ListNode) p.getNext();
            i++;
        }
    }

    @Override
    public int indexOf(Object element) {
        int i = 0;
        ListNode p = head;
        while(p!=null){
            if(p.getData().equals(element)){
                return i;
            }
            p = (ListNode) p.getNext();
            i++;
        }
        return -1;//整个链表中并没有对应的元素，则返回-1
    }

    @Override
    public Object elementAt(int target) {
        if(target<0||target>=size){
            System.out.println("索引越界,已经超过链表的元素个数");
            return null;
        }
        int i = 0;
        ListNode p = head;
        while (p!=null) {
            if (i == target) {
                return p.getData();
            }
            p = (ListNode) p.getNext();
            i++;
        }
        return null;
    }

    @Override
    public Object elementPrior(int index) {
        //索引越界
        if(index-1<0||index>size){
            return null;
        }
        int i =0;
        ListNode p = head;
        while (p!=null){
            if (i==index-1){
                return p.getData();
            }
            p = (ListNode) p.getNext();
            i++;
        }
        return null;
    }

    @Override
    public Object elementNext(int index) {
        //索引越界
        if(index<0||index+1>size){
            return null;
        }
        int i =0;
        ListNode p = head;
        while (p!=null){
            if (i==index+1){
                return p.getData();
            }
            p = (ListNode) p.getNext();
            i++;
        }
        return null;
    }

    @Override
    public boolean contains(Object element) {
        ListNode p = head;
        while (p!=null){
            if(p.getData().equals(element)){
                return true;
            }
            p = (ListNode) p.getNext();
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        ListNode p = head;
        while (p!=null){
            stringBuilder.append(p.getData());
            if(p.getNext()!=null){
                stringBuilder.append(",");
            }
            p = (ListNode) p.getNext();
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }


    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list);
        list.delete("c");
        System.out.println(list);
        list.delete("a");
        System.out.println(list);
        list.delete("g");
        list.update(0,"x");
        System.out.println(list);
        list.delete(0);
        System.out.println(list);
        list.delete(10);
        list.update(3,"a");
        list.add("a");
        System.out.println(list);
        list.contains("a");
        System.out.println(list.elementAt(2));
        System.out.println(list.indexOf(1));
        System.out.println(list.indexOf("d"));
        System.out.println(list.indexOf("e"));
        list.add("b");
        list.add("g");
        System.out.println(list);
        System.out.println(list.elementPrior(1));
        System.out.println(list.elementNext(3));
        System.out.println(list.elementNext(5));
    }
}

这里mian方法最后的输出为：

线性表的总结

结合上一篇的顺序存储的总结java数据结构，线性表顺序存储（数组）的实现

对于顺序存储，按顺序放在一起，相邻元素通过内存地址相邻产生联系，”随机存取“。
而链式存储，元素随机放置在内存中任意位置，每个元素除了存放数据，也保存了其相邻元素的内存地址，来实现线性关系，“随机存取”。
单链表的存储空间会比相同元素个数的线性表多，原因是单链表中包括了数据域data和指针域next,所以其存储密度是小于1的。

对与线性表中的基本操作的时间复杂度

1.查找元素，按值查找。

给定长度为 n 的线性表，查找值为 v 的元素。(最坏)从头到尾遍历 => 时间复杂度O(n)

2.新增或者删除元素

对于顺序表来说，新增或者删除元素，需要对应的右移或者左移，最坏的情况是挪动所有元素的位置，时间复杂度为O(n)，空间复杂度为O(1).
对于单链表来说，新增或者删除元素，只需要修改前驱元素的next即可。因线性链表在插⼊或删除时，不需要移动元素，只要修改指针，⼀般情况下时间复杂度为O(1)。但是，如果要在单链表中进⾏前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。进⾏插⼊和删除的操作是常数即便，但是寻找前驱才要O(n)。空间复杂度为O(1).

3.更新元素