linkedlist底层是双向链表吗?java linkedlist底层实现原理详解

KLQ 2020-06-03 15:09:46 java常见问答 5465

对于linkedlist底层实现原理你了解吗?linkedlist底层实现原理是通过链表来实现的吗?下面一起来详细的了解一下吧。

是的,我们要清楚的知道,linkedlist底层就是通过链表来实现的。

下面再来详细的给你介绍一下相关知识。

首先我们要深入了解一下链表,链表的单元是节点,除此之外,链表是由多个节点所构成的,每一个节点都涵盖了3个部分,分别是头部指向上的一个节点,中部指向这个节点,尾部指向下一个节点。

双向链表,这里应该都看得明白吧。

linkedlist底层是双向链表吗

下面再来谈一下优点和缺点:

1、优点,插入和删除的效率快

2、缺点:添加慢

再来谈一下源码的实现(单链)

package test2;
//节点类
public class Node
{
    // 数据值
    private Object obj;
    // 下一个节点的内存地址
    private Node nextnode;
    public Node getNextnode()
    {
        return nextnode;
    }
    public void setNextnode(Node nextnode)
    {
        this.nextnode = nextnode;
    }
    public Object getObj()
    {
        return obj;
    }
    // 无参构造
    public Node()
    {
        super();
    }
    // 有参构造
    public Node(Object obj)
    {
        this.obj = obj;
    }
    @Override
    public String toString()
    {
        return "Node [obj=" + obj + ", next=" + nextnode + "]";
    }
}
package test2;
//实现类
public class MyLinkedList
{
    // 第一个节点
    private Node firstNode;
    // 节点的个数
    private int size;
    // 添加节点
    public void add(Object obj)
    {
        // 封装一个节点
        Node node = new Node(obj);
        // 1.判断是否第一个节点
        if (firstNode == null)
        {
            // 2.为空,直接把封装好的节点传入
            firstNode = node;
        }
        else
        {
            // 3.不为空,说明里面有节点 就遍历 拿到nextNode为空的节点
            Node nextnode2 = firstNode;
            while (nextnode2.getNextnode() != null)
            {
                nextnode2 = nextnode2.getNextnode();
            }
            // 4.拿到之后传值
            nextnode2.setNextnode(node);
        }
        // 记录节点个数
        size++;
        // System.out.println("进来了" + size);
    }
    // 删除节点
    // a.删除指定索引处的元素
    public void deleteByIndex(int index)
    {
        // 判空
        if (index < 0 || index > size - 1)
        {
            throw new RuntimeException("索引值不正确,请重新输入!");
        }
        // 获取正在被干掉的节点的前一个节点
        Node pronode = null;
        // 获取正在执行的节点
        Node node = firstNode;
        for (int i = 0; i < index; i++)
        {
            pronode = node;
            node = node.getNextnode(); // 获取正在被干掉的节点
        }
        // 索引为0
        if (index == 0)
        {
            firstNode.setNextnode(node.getNextnode());
        }
        else
        {
            // 索引不为0
            pronode.setNextnode(node.getNextnode());
        }
    }
    // b.删除指定的元素
    public void deleteByObj(Object obj)
    {
        deleteByIndex(getIndexByObj(obj));
    }
    // 按照索引查出对应的元素
    public Object findObjByIndex(int index)
    {
        // 判空
        if (index < 0 || index > size - 1)
        {
            throw new RuntimeException("索引值不正确,请重新输入!");
        }
        Node node = firstNode;
        for (int i = 0; i < index; i++)
        {
            node = node.getNextnode();
        }
        return node.getObj();
    }
    // 指出指定元素的第一次出现的索引
    public int getIndexByObj(Object obj)
    {
        Node node = firstNode;
        int index = 0; // 定义索引
        while (node != null)
        {
            if (node.getObj()
                .equals(obj))
            {
                return index;
            }
            node = node.getNextnode();
            index++;
        }
        return -1;
    }
    // 查询节点个数
    public int list()
    {
        return size;
    }
    @Override
    public String toString()
    {
        // 字符串拼接
        StringBuilder sb = new StringBuilder("[");
        // 创建一个临时变量
        Node node = firstNode;
        while (node.getNextnode() != null)
        {
            sb.append(node.getObj());
            sb.append(",");
            node = node.getNextnode();
        }
        sb.append(node.getObj());
        sb.append("]");
        return sb.toString();
    }
}
package test2;
//测试类
public class Test
{
    public static void main(String[] args)
    {
        MyLinkedList list = new MyLinkedList();
        list.add(1);
        list.add("hello");
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(2);
        list.add(2);
        list.deleteByIndex(2);
        System.out.println(list.findObjByIndex(1));
        System.out.println(list.getIndexByObj(2));
        System.out.println("节点个数为:" + list.list());
        System.out.println(list.getIndexByObj(3));
        System.out.println(list);
        list.deleteByObj(3);
        System.out.println(list);
    }
}

以上内容仅供参考,你还想了解更多的相关内容吗?请继续通过本站的常见问题栏目来了解吧。

推荐阅读:

linkedlist类的特点,有什么特点?

java List和Set的区别是什么?有什么区别?

Linkedlist是每次遍历都从第一个吗?有多少种遍历方式?