java数据结构中单向链表和双向链表的介绍

这篇文章主要讲解了“java数据结构中单向链表和双向链表的介绍”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“java数据结构中单向链表和双向链表的介绍”吧！

目录

• 单向链表

• 单链表图解

• 代码

• 双向链表

• 编码

单向链表

单向链表比顺序结构的线性表最大的好处就是不用保证存放的位置，它只需要用指针去指向下一个元素就能搞定。

单链表图解

图画的比较粗糙，简单的讲解一下：

上面四个长方形，每个长方形都是一个节点。在长方形中，一种包含两个东西，一个是当前节点的元素，一个是指向下一节点的地址。这个下一个节点的地址指向了下一个节点中的元素。以此类推。

在最左边的叫做头节点，同样，最后面的叫尾节点。

所以，我们所有的操作都是根据节点来进行操作。

代码

这些代码都有很详细的注释，我就不做过多的解释了，你直接到本地idea运行一遍就全部知道了。

package com.zxy.lianbiao;public class MySinglyLinkedList<E> implements MyList<E> {        class Node<E> {        private E item; // 存储元素        private Node next; // 存储下一个节点对象        public Node(E item, Node next) {            this.item = item;            this.next = next;        }    }    private Node head; // 存放链表中的头节点    private int size; // 记录元素的个数        @Override    public void add(E element) {        // 创建节点        Node<E> node = new Node<>(element, null);        // 找到尾节点        Node tail = getTail();        // 节点的挂接        if (tail == null) { // 如果没有尾节点，那意思就是头节点都不存在            // 没有头节点，那么就把创建的节点给头节点            this.head = node;        } else {            tail.next = node;        }        // 记录元素的个数        this.size++;    }        private Node getTail() {        // 判断头节点是否存在        if (this.head == null) {            return null;        }        // 查找尾节点        Node node = this.head;        while (true) {            if (node.next == null) {                break;            }            node = node.next; // 移动指针指向下一个        }        return node;    }        @Override    public E get(int index) {        // 校验index的合法性        this.checkIndex(index);        // 根据位置获取指定节点        Node<E> node = this.getNode(index);        // 将该节点中的元素返回        return node.item;    }        private void checkIndex(int index) {        // 0<=index<size        if (!(index >= 0 && index < this.size)) {            throw new IndexOutOfBoundsException("Index: " + index + "   this.size: " + this.size);        }    }        private Node<E> getNode(int index) {        Node<E> node = this.head;        for (int i = 0; i < index; i++) {            node = node.next;        }        return node;    }        @Override    public int size() {        return this.size;    }        @Override    public E remove(int index) {        // 校验index合法性        this.checkIndex(index);        // 根据位置找到节点对象        Node<E> node = getNode(index);        // 获取该节点对象中的元素        E item = node.item;        // 将该节点对象从单向链表中移除        // 判断当前删除的节点是否为头节点        if (this.head == node) {            this.head = node.next;        } else {            Node<E> temp = this.head;            for (int i = 0; i < index - 1; i++) {                temp = temp.next; // 此时的temp就是要删除的那个节点的前一个节点            }            temp.next = node.next; // 将当前节点的前一个节点指向当前节点的后一个节点        }        // 然后将当前节点的下一个节点指向null        node.next = null;        // 记录元素个数        this.size--;        // 将该元素返回        return item;    }        public void insert(int index, E element) {        // 先根据要插入的位置拿到这个位置的节点对象        Node<E> item = getNode(index);        // 根据插入的元素新建一个节点        Node<E> eNode = new Node<>(element, null);        // 如果是头节点，那么就找不到前一个，直接把这个赋值给head        if (index == 0){            // index==0代表是替换掉头节点            this.head = eNode;            eNode.next = item;            this.size++;        }else {            // 根据当前的节点对象去找到前一个节点对象和后一个节点对象            Node<E> before = this.head; // 根据头节点去找            for (int i = 0; i < index - 1; i++) {                before = before.next; // 此时的before就是当前节点的前一个节点            }            before.next = eNode;            eNode.next = item;            this.size++;        }    }    public static void main(String[] args) {        MySinglyLinkedList<String> list = new MySinglyLinkedList<>();        System.out.println("添加节点开始------------------------");        list.add((String) "a");        list.add((String) "b");        list.add((String) "c");        list.add((String) "d");        System.out.println("添加节点完成-------------------------\n");        System.out.println("插入指定的元素");        list.insert(0,"f");        for (int i = 0; i < list.size; i++) {            System.out.println(list.get(i));        }    }}

双向链表

昨天写完单向链表和栈结构之后，看了看程杰大大的书中有介绍双向链表的部分。虽然是c语言写的，但是我还是用Java给翻译出来了。

思路如下：

首先，双向链表和单向链表的最大区别就是，双向链表比单链表多了个指向前一节点的指针。代码量其实并不比单链表多很多，只是思路的转变需要克服一下。

其次就是在插入元素的时候，我们可以在链表的头部插入，也可以在链表的尾部插入（因为有两个指针嘛）

编码

代码其实和单链表差不多，如果感兴趣的话可以去看看我之前写的单链表的文章。虽然文笔很烂，但是代码货真价实。

package com.zxy.lianbiao;public class MyDoublyLinkedList<E> implements MyList<E> {        class Node<E> {        E item; // 记录元素        Node<E> prev; // 记录前一个节点对象        Node<E> next; // 记录下一个节点对象        public Node(Node<E> prev, E item, Node<E> next) {            this.item = item;            this.prev = prev;            this.next = next;        }    }    private Node head; // 记录头节点    private Node tail; // 记录尾节点    private int size; // 记录元素个数        @Override    public void add(E element) {        linkLast(element);    }        private void linkLast(E element) {        Node t = this.tail; // 获取尾节点        Node<E> node = new Node<>(t, element, null); // 创建节点对象        this.tail = node; // 将新节点定义为尾节点 因为原来的尾节点被这个新节点替代了        if (t == null) {            // 说明一个节点都没有，这个还得是头节点            this.head = node;        } else {            t.next = node;        }        this.size++;    }        @Override    public E get(int index) {        this.checkIndex(index);        // 根据位置查找节点对象        Node<E> node = this.getNode(index);        return node.item;    }        private void checkIndex(int index) {        if (!(index >= 0 && index < this.size)) {            throw new IndexOutOfBoundsException();        }    }        private Node getNode(int index) {        // 判断当前位置距离头或者尾哪个节点更近  使用二分法        if (index < (this.size >> 1)) {            Node node = this.head;            for (int i = 0; i < index; i++) {                node = node.next;            }            return node;        } else {            Node node = this.tail;            for (int i = this.size - 1; i > index; i--) {                node = node.prev;            }            return node;        }    }        @Override    public int size() {        return this.size;    }        @Override    public E remove(int index) {        // 对index进行合法性校验        this.checkIndex(index);        Node node = this.getNode(index); // 根据位置获取到节点对象        // 获取节点对象的元素        E item = (E) node.item;        // 判断当前节点是否为头节点        if (node.prev == null) {            this.head = node.next;        } else {            node.prev.next = node.next;        }        // 判断当前节点是否为尾节点        if (node.next == null) {            // node.prev.next = null;            this.tail = node.prev;        } else {            node.next.prev = node.prev;        }        // 当前节点断掉与他后继节点的连接        node.next = null;        // 当前节点断掉与直接前驱节点的连接        node.prev = null;        node.item = null;        this.size--;        return item;    }        public void addFirst(E element) {        this.linkFirst(element);    }        public void linkFirst(E element) {        // 获取头节点对象        Node head = this.head;        Node<E> eNode = new Node<>(null, element, head);        // 将新节点定义为头节点        this.head = eNode;        if (head == null) {            // 如果为空，说明该链表中一个节点都没有 也就是该头节点也是尾节点            this.tail = eNode;        } else {            head.prev = eNode;        }        this.size++;    }        public void addLast(E element) {        this.linkLast(element);    }    public static void main(String[] args) {        MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>();        list.add("a");        list.add("b");        list.add("c");        list.add("d");        list.add("e");        System.out.println(list.remove(2));        System.out.println(list.size);        for (int i = 0; i < list.size(); i++) {            System.out.println(list.get(i));        }    }}

感谢各位的阅读，以上就是“java数据结构中单向链表和双向链表的介绍”的内容了，经过本文的学习后，相信大家对java数据结构中单向链表和双向链表的介绍这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！