美文网首页
手写LinkedList

手写LinkedList

作者: 长孙俊明 | 来源:发表于2019-10-26 16:13 被阅读0次

LinkedList是双向链接数据结构,插入和删除快,查询慢,因为他使用了二分查找。

public class ExtLinkedList<E> {

    private Node first;

    private Node last;

    private int size;

    public void add(E o) {
        Node l = last;
        Node node = new Node(o, l, null);
        last = node;
        if(l == null) {
            first = node;
        } else {
            l.next = node;
        }
        size++;
    }

    public Node<E> get(int index) {

        if(index < (size >> 1)) {
            Node x = first;
            for(int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node x = last;
            for(int i = size - 1; i > index; i--) {
                x = x.pre;
            }
            return x;
        }
    }

    public Node remove(int index) {
        Node node = get(index);
        unlink(node);
        return node;
    }

    private void unlink(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        if(pre == null) {
            first = next;
        } else {
            pre.next = next;
            node.pre = null;
        }
        if(next == null) {
            last = pre;
        } else {
            next.pre = pre;
            node.next = null;
        }
        node.item = null;
        size--;
    }

    public static void main(String[] args) {
        ExtLinkedList<String> tests = new ExtLinkedList<String>();
        tests.add("a");
        tests.add("b");
        tests.add("c");
        Node node = tests.get(0);
        System.out.println(node.item);
        node = tests.remove(1);
        for(int i = 0; i < tests.size; i++) {
            System.out.println(tests.get(i).item);
        }
    }


    static class Node<E> {
        E item;
        Node<E> pre;
        Node<E> next;
        public Node(E item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

}

相关文章

  • 手写LinkedList

    LinkedList是双向链接数据结构,插入和删除快,查询慢,因为他使用了二分查找。

  • Java学习——day 09

    主要内容 容器的简介 ArrayList简介 手写模仿ArrayList 手写模仿LinkedList 笔记详情 ...

  • 手写简单的LinkedList

    设计上比之前的 手写ArrayList 更进一步的仿照源码,更加面向对象。 我对源码中这部分设计的理解:接口用于定...

  • 手写LinkedList(双向链表)

    系统jdk里的LinkedList是由一个个节点连接起来的,节点就相当于一个对象,里面有数据域和指针域,数据域是存...

  • 生产者和消费者

    自己实现这个队列,取出一个,移动一个,还要内存移动?NM,LinkedList来完成这个过程。 NM,人家就手写。...

  • 手写双向循环列表LinkedList

    废话不多说,直接上代码。

  • JavaSE Day16 集合

    一、 ArrayList VS LinkedList 1. 什么是 LinkedList? LinkedList ...

  • LinkedList简介

    LinkedList简介 LinkedList基于双向链表实现 LinkedList相对于Arraylist来说,...

  • java 集合 2 - LinkedList

    java 集合 2 - LinkedList 参考文章:图解集合2:LinkedList LinkedList是基...

  • LinkedList

    eg:LinkedList link = new LinkedList();

网友评论

      本文标题:手写LinkedList

      本文链接:https://www.haomeiwen.com/subject/jgfuvctx.html