手写双向链表

双向链表,又称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

根据自己需求写对应的链表存储 可以节约内存空间,不必使用一些用不到算法。

/**
 * Created by zqb on 2019/5/21
 */
public class LinkedList<E> {
    /**
     * 节点
     *
     * @param <E>
     */
    private static 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;
        }
    }

    public LinkedList() {

    }

    //头节点 尾节点
    private Node<E> first;
    private Node<E> last;
    //大小
    int size;

    /**
     * 添加数据到最后
     */
    public void add(E e) {
        linkLast(e);
    }

    /**
     * 添加数据在index 位置
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == size) {//如果添加到最后
            linkLast(e);
        } else {
            //查找当前位置所在的节点
            Node<E> target = node(index);
            //原节点的上一节点
            Node<E> pre = target.prev;
            //更新新节点的上一节点
            Node<E> newNode = new Node<>(pre, e, target);
            if (pre == null) { //如何添加的位置 为0  前位置为null
                first = newNode;
                //更新原位置节点的上一个节点
                target.prev = newNode;
            } else {
                //更新原前节点的下一个节点
                pre.next = newNode;
                //更新原位置节点的上一个节点
                target.prev = newNode;
            }
            size++;
        }
    }

    private void linkLast(E e) {
        Node<E> newNode = new Node<E>(last, e, null);
        Node<E> l = last;
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 查找位置
     */
    public E get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        return node(index).item;

    }

    /**
     * 获取index位置上的节点
     *
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        //如果index 在整个链表的前半部分
        if (index < (size / 2)) {//size >>1
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }

    }

    /**
     * 获取数据e位置上的节点
     *
     * @param e
     * @return
     */
    private Node<E> node(E e) {
        Node<E> node = first;
        boolean isHaveNode = false;
        for (int i = 0; i < size; i++) {
            if (node.item == e) {
                isHaveNode = true;
                break;
            }
            node = node.next;
        }
        if (isHaveNode) {
            return node;
        } else {
            return null;
        }
    }

    /**
     * 删除元素 根据index
     */
    public void remove(int index) {
        Node<E> target = node(index);
        unLinkNode(target);
    }

    /**
     * 删除元素
     */
    public void remove(E e) {
        Node<E> target = node(e);
        unLinkNode(target);
    }

    /**
     * 删除节点
     *
     * @param target
     */
    private void unLinkNode(Node<E> target) {
        if (target == null) {
            System.out.println("没有该数据");
            return;
        }
        Node<E> pre = target.prev;
        Node<E> next = target.next;
        if (pre != null) {
            if (next != null) {
                pre.next = next;
                next.prev = pre;
            } else { //下一节点为空  则把要删除的节点的上一节点 设置为结束节点
                pre.next = null;
                last = pre;
            }
        } else { //前一节点为空  则把要删除的节点的下一节点 设置为开始节点
            if (next != null) {
                next.prev = null;
                first = next;
            }
        }
        size--;
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 5,994评论 0 13
  • 双向链表是指每个节点都包含两个指针分别指向其前驱和后继的链表,双向链表在遍历时更灵活,可以向前或向后遍历,在查找元...
    怀念小兔阅读 827评论 0 0
  • 目录 1、属性 2、链表和数组的区别 2.1、数组概述 2.2、数组和链表优缺点 2.3、链表和数组的比较 3、单...
    我哈啊哈啊哈阅读 2,850评论 1 41
  • 链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢? 可以...
    rainchxy阅读 2,040评论 0 6
  • 前言 在之前的文章中, 大家还记得我的链表和结点、结点协议的名字么? 1.CHRSinglyLinkedListN...
    Chrisss阅读 1,597评论 3 3