[数据结构与算法]手写单链表代码部分解析

1.关于单链表

特点： 数据元素的存储对应的是不连续的存储空间。
每个结点是由数据域和指针域组成。
逻辑上相邻的节点物理上不必相邻。

缺点：
比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
按照索引查找效率低下。

优点：
插入、删除灵活
有元素才会分配结点空间，不会有闲置的结点。

2. 单链表的源码解析

（1）定义一个List接口

public interface List {
    public int size();// 返回线性表的大小，即数据元素的个数。
    public Object get(int i);  // 返回线性表中序号为 i 的数据元素
    public boolean isEmpty();// 如果线性表为空返回 true，否则返回 false。
    public boolean contains(Object e); // 判断线性表是否包含数据元素 e
    public int indexOf(Object e); // 返回数据元素 e 在线性表中的序号
    public void add(int i, Object e);  // 将数据元素 e 插入到线性表中 i 号位置
    public void add(Object e);// 将数据元素 e 插入到线性表末尾
    public boolean addBefore(Object obj, Object e);  // 将数据元素 e 插入到元素 obj 之前
    public boolean addAfter(Object obj, Object e); // 将数据元素 e 插入到元素 obj 之后
    public Object remove(int i); // 删除线性表中序号为 i 的元素,并返回之
    public boolean remove(Object e);   // 删除线性表中第一个与 e 相同的元素
    public Object replace(int i, Object e);  // 替换线性表中序号为 i 的数据元素为 e，返回原数据元素
    public Iterator iterator(); //迭代List
}

（2）创建一个节点类Node

public class Node {
    Object data;//存储数据
    Node next;//指向下个节点的指针
    public Node() {//构造方法 
    }
    public Node(Object data) {//有参的构造方法 
        this.data = data;
    }
    public Node(Object data, Node next) {//有参构的构造方法
        this.data = data;
        this.next = next;
    }
   public Object getData() {
        return data;
    }
    public void setData(Object data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }

(3)定义一个SingleLinkedList，实现List接口

package com.yue.list2;
import com.yue.list.Iterator;
public class SingleLinkedList implements List {
    private Node head = new Node();//创建头节点
    private int size;//节点数量,默认为0（不包括头节点）
    @Override
    public int size() {
        return size;
    }
    @Override
    public Node get(int i) {
        if (i < 0 || i > size) {
            throw new RuntimeException("索引越界");
        }
        Node p = head; //定义一个指针，指向头节点
        //循环i+1次，找到索引为i的节点
        for (int j = 0; j <= i; j++) {
            p = p.next;//指向下一个节点
        }
        //返回第i个节点
        return p;
    }
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    @Override
    public boolean contains(Object e) {
        return indexOf(e) >= 0;
    }
    @Override
    public int indexOf(Object e) {
        return 0;
    }
    @Override
    public void add(int i, Object e) {
        //先获取第i-1个元素(如果i=0，就是获取头节点)
        Node p = head;
        if (i > 0) {
            p = get(i - 1);
        }
        Node newNode = new Node(e);   //新建一个节点，并加入数据
        newNode.next = p.next;//指定新节点的下一个节点
        p.next = newNode;  //前一个结点的下一个节点是当前节点
        size++;
    }
    @Override
    public void add(Object e) {//加到末尾
        add(size, e);
    }
    @Override
    public boolean addBefore(Object obj, Object e) {
        return false;
    }
    @Override
    public boolean addAfter(Object obj, Object e) {
        return false;
    }
    @Override
    public Object remove(int i) {
        //先获取第i-1个元素(如果i=0，就是获取头节点)
        Node p = head;
        if (i > 0) {
            p = get(i - 1);
        }
        Node currentNode = p.next; //指向当前第i个节点
        p.next = p.next.next;   //让第i-1个节点的下一个节点是第i+1个节点
        currentNode.next = null;      //第i个节点没有下一个节点
        size--;
        return null;
    }
    @Override
    public boolean remove(Object e) {
        return false;
    }
    @Override
    public Object replace(int i, Object e) {
        return null;
    }
    @Override
    public Iterator iterator() {
        return null;
    }
    public String toString() {
        StringBuilder builder = new StringBuilder("[");
//        for (int i = 0; i < size; i++) {
//            Node node = get(i);//注意这里用get方法效率极低，因为设计索引
//            builder.append(node.data + ",");
//
//        }
        Node p = head;
        for (int i = 0; i < size; i++) {
            p = p.next;//p指向第i个节点
            builder.append(p.data + ",");
        }
        if (size != 0) {
            builder.deleteCharAt(builder.length() - 1);//去除末尾的逗号
        }
        builder.append("]");
        return builder.toString();
    }
}

（4）测试类TestList

public class TestList {
    public static void main(String[] args) {
        //创建线性顺序表
        List list = new SingleLinkedList();
        //向末尾添加元素
        list.add("11111");
        list.add("aaaaa");
        list.add("bbbbb");
        list.add("33333");
        list.add("22222");
        list.add(3, "AAAAA");
        System.out.println(list.get(0));
        list.remove(2);
        //进行各种操作验证添加
        System.out.println(list.size());
        System.out.println(list.get(0));
        System.out.println(list.isEmpty());
        System.out.println(list.contains("44444"));
        System.out.println(list.indexOf("22222"));
        System.out.println(list.toString());
    }
}

运行结果