欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-06 12:33:31
...

链表的基本结构

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

单链表的基本实现

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());//取得链表长度
    }
}

运行结果:
链表的实现(单链表、双链表)