java数据结构基础:单,双向链表

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));
        }
    }
}

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));
        }
    }
}