02.Java数据结构与算法之单链表

认识单链表

特点

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

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

缺点

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

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

优点：

          1.插入、删除灵活 (不必移动节点，只要改变节点中的指针)。

          2.有元素才会分配结点空间，不会有闲置的结点。

添加节点

删除节点

带头节点的单链表

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

          在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点

          可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。 一个不带头结点和带头结点的单链表实现线性表的结构图如图所示。

定义List接口

public interface List <T>{
    // ------- 添加 -------
    void add(Object object);

    // ------- 根据坐标删除 -------
    void remove(int index);

    // ------- 根据内容删除 -------
    void removeobj(Object object);

    // ------- 取出数据 -------
    Object get(int index);

    // ------- 求集合的长度 -------
    int size();

    // ------- 判断集合是否为空 -------
    boolean isEmpty();

    // ------- 根据内容找到元素坐标 -------
    int IndexOf(Object object);

    // ------- 判断元素是否存在 -------
    boolean contions(Object object);

    // ------- 根据坐标位置插入元素 -------
    void add(int index, Object object);

    // ------- toString -------
    String toString();
}

SingLinkList实现类

import java.util.NoSuchElementException;

public class SingleLinkedList implements List{
    private Node head = new Node();  //头节点
    private int size;   //链表的结点数量

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("[");
        Node p = head.next;
        while(p != null){
            stringBuilder.append(p.data + ",");
            p = p.next;
        }
        //最后一个逗号删掉
        stringBuilder.deleteCharAt(stringBuilder.length()-1);
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    @Override
    public void add(Object object) {
        //先让p指向头节点
        Node p = head;
        //将p移动到最后一个结点
        while(p.next != null){
            p = p.next;
        }
        //添加元素
        p.next = new Node(object);
        size++;
    }

    @Override
    public void remove(int index) {
        
        if(index < 0||index > size-1){
            throw  new NoSuchElementException();
        }
        ////要删除的前一个结点
        Node prev = (Node) getNode(index - 1);
        //当前要删除的结点
        Node currNode = prev.next;
        Node nextNode = currNode.next;
        prev.next = nextNode;
        currNode.next = null;
        size--;
    }

    @Override
    public void removeobj(Object object) {
        int index = IndexOf(object);
        if(index >=0){
            remove(index);
        }
    }

    @Override
    public Object get(int index) {
        Node o = (Node)getNode(index);
        return o.data;
    }
    public Object getNode(int index) {
        
        if(index < 0||index > size-1){
            throw  new NoSuchElementException();
        }
        // 指向了第一个结点
        Node p=head.next;
        for (int i = 0; i <index ; i++) {
            p=p.next;
        }
        // 返回的是p结点
        return p;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public int IndexOf(Object object) {
        //判断是否找到
        int index = -1;
        Node p = head.next;
        while(p != null){
            index++;
            if(p.data == object || p.data.equals(object)){
                return index;
            }
            p = p.next;
        }
        return -1;
    }

    @Override
    public boolean contions(Object object) {
        return IndexOf(object) >= 0;
    }

    @Override
    public void add(int index, Object object) {
        //判断索引是否合法,这里允许等于size,因为这样就可以往最后一个位置添加
        if(index<0||index > size){
            throw  new NoSuchElementException();
        }
        //获取添加位置的前一个节点
        Node prev=(Node) getNode(index - 1);
        Node newNode = new Node(object,prev.next);
        prev.next = newNode;
        size++;
    }

    //将Node作为单链表的内部类来使用
    class Node {
        Object data;//存储是数据
        Node next;//指向下个节点的指针
        public Node() {

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

        public String toString() {
            return "Node [data=" + data + ", next=" + next + "]";
        }
    }
}