链表的实现(单链表、双链表)

链表的基本结构

链表知识的引入：
对于之前我们接触到的数组知识，要想保存多个对象，首先想到的一定是对象数组。
但是数组是一个长度固定的线性结构，一旦内容不足或者过多，都会在成内存资源的浪费，由此引入链表充分解决资源浪费问题。

单链表的基本实现

class Node{
    private Node next;//指向下一个结点
    private Object data;//结点保存的数据

    public Node(Object data){
        this.data = data;//对结点进行赋值
    }
    //private属性需要设置getter setter方法
    public Node getNext() {
        return next;
    }

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

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }
}
public class List {
    public static void main(String[] args) {
        //初始化结点
        Node root = new Node("首结点");
        Node node1 = new Node("结点A");
        Node node2 = new Node("结点B");
        Node node3 = new Node("结点C");

        //对结点进行next赋值
        root.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);

        //获取结点的值
        getNodeData(root);//当前节点为首结点
    }
    public static void getNodeData(Node node){
        if(node != null){
            System.out.println(node.getData());//打印当前节点的值
            getNodeData(node.getNext());//递归调用当前节点的写一个节点
        }
    }
}

运行结果：

在以上整个链表的实现过程中可以看出，Node类的核心作用就是实现节点数据保存和节点连接问题。
当用户调用时需要自己进行节点的创建和节点挂载，比较麻烦，所有此时引入一个单独的Link类，通过Link了实现数据保存以及节点关系挂载

引入单独Link类实现双向链表：

//定义Link接口
interface Link{
    void add(Object obj);
    boolean remove(int index);
    boolean set(int index, Object obj);
    Object get(int index);
    int contains(Object obj);
    void clear();
    void printLink();
    int length();
    Object[] toArray();
}
//实现LInk接口
class LinkImpl implements Link{
    private Node first;//头结点
    private Node last;//尾结点
    private int size = 0;//初始化链表长度为0

    private class Node{
        private Node prev;//前驱节点
        private Object data;//节点保存数据
        private Node next;//后继节点
        //实现节点数据的初始化
        public Node(Node prev, Object data, Node next){
            super();
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }

    @Override
    //增加节点
    public void add(Object obj) {
        Node temp = this.last;
        Node newNode = new Node(temp, obj, null);
        this.last = newNode;
        if(this.first == null){
            this.first = newNode;
        }else {
            temp.next = newNode;
        }
        this.size++;//链表长度增加
    }

    @Override
    public boolean remove(int index) {
        if(!isLinkElement(index)){
            return false;
        }
        Node node = node(index);
        if(node == this.first){
            if(node == this.last){
                node = null;
                this.size--;
                return true;
            }else {
                Node temp = this.first;
                this.first = node.next;
                temp.next = null;
                this.first.prev = null;
                this.size--;
                return true;
            }
        }
        else if(node == this.last){
            Node temp = this.last;
            this.last = node.prev;
            temp.prev = null;
            this.size--;
            return true;
        }
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = node.next = null;
        this.size--;
        return true;
    }

    @Override
    public boolean set(int index, Object obj) {
        if(isLinkElement(index)){
            return false;
        }
        Node node = node(index);
        node.data = obj;
        return true;
    }

    @Override
    public Object get(int index) {
        if(isLinkElement(index)){
            return null;
        }
        return node(index).data;
    }

    @Override
    //取得当前节点的下标
    public int contains(Object obj) {
        if(obj == null){
            int index = 0;
            for(Node x = this.first; x != null; x = x.next){
                if(x.data == null){
                    return index;
                }
                index++;
            }
            return -1;
        }else {
            int index = 0;
            for(Node x = this.first; x != null; x = x.next){
                if(obj.equals(x.data)){
                    return index;
                }
                index++;
            }
            return -1;
        }
    }

    @Override
    //节点删除
    public void clear() {
        for(Node x = this.first; x != null; ){
            Node temp = x.next;
            x.prev = x.next = null;
            x = temp;
        }
        this.first = this.last = null;
        this.size--;
    }

    @Override
    public void printLink() {
        Object[] result = this.toArray();
        for(Object object : result){
            System.out.println(object);
        }
    }

    @Override
    //取得链表长度
    public int length() {
        return this.size;
    }

    @Override
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for(Node temp = first; temp != null; temp = temp.next){
            result[i++] = temp.data;
        }
        return result;
    }

    // 仅用于LinkImpl类内部
    private Node node(int index) {
        if (index < (size >> 1)) {
            Node result = this.first;
            for(int i = 0 ; i< index ; i++) {
                result = result.next;
            }
            return result;
        }
        Node result = this.last;
        for(int i = size-1 ; i > index ; i--) {
            result = result.prev;
        }
        return result;
    }
    private boolean isLinkElement(int index) {
        return index>=0 && index<size;
    }
}

//定义工厂类,用于用户调用
class Factory{
    private Factory(){}
    public static Link getLinkInstance(){
        return new LinkImpl();
    }
}

public class ListTest {
    public static void main(String[] args) {
        Link link = Factory.getLinkInstance();
        link.add("头结点");//节点插入
        link.add("结点A");
        link.add("结点B");
        link.add("结点C");
        //link.clear();
        System.out.println(link.contains("结点B"));//取得节点下标
        System.out.println(link.contains("abc"));
        System.out.println(link.length());//取得链表长度
    }
}

运行结果：