>

LinkedList封装

- 编辑:金沙国际平台登录 -

LinkedList封装

LinkedList简单的包裹

package com.cn.test.jihe.LinkedList;import java.util.NoSuchElementException;public class LinkedList {    // 头结点    Node<Object> first;    // 尾指针    Node<Object> last;    private int size; // 记录要插入的元素的总数    LinkedList() {    }    /**     * 将指定元素添加到此列表的结尾。     *      * @param obj     * @return insert     */    boolean add(Object obj) {        linkLast;        return true;    }    private void linkLast(Object obj) {        Node l = last;        Node<Object> newNode = new Node<Object>(l, obj, null);        last = newNode; // 记录下次要插入的前驱节点        if (l == null) {            first = newNode;        } else {            l.next = newNode;        }        size++;    }    /**     * 在此列表中指定的位置插入指定的元素。     *      * @throws Exception     *             insert     */    void add(int index, Object element) throws Exception {        // 判断要插入的位置        rangeCheckIndex;        // 循环遍历要插入的位置        insertElement(index, element);        size++;    }    private void insertElement(int index, Object element) {        int count = 0;        Node temp = first;        // 在头部进行插入        if (index == 0) {            if (temp != null) {                Node newNode = new Node(null, element, temp);                temp.prev = newNode;                first = newNode;            } else {                Node tempLast = last;                Node newNode = new Node(tempLast, element, null);                last = newNode;                first = newNode;            }            return;        }        // 在尾部进行插入        if (index != 0 && index == size) {            Node tempLast = last;            Node newNode = new Node(tempLast, element, null);            last = newNode;            tempLast.next = newNode;            return;        }        // 不是在头部或者尾部进行插入        while (temp != null) { //            if (count == index) {                // 找到要插入的位置 temp这个节点表示要插入的节点的位置                Node newNode = new Node(temp.prev, element, null);                newNode.prev.next = newNode;                temp.prev = newNode;                newNode.next = temp;            }            temp = temp.next;            count++;        }    }    private void rangeCheckIndex(int index) throws Exception {        if (index < 0 || index > size)            throw new Exception("下标越界");    }    /**     * 返回列表中指定的元素     *      * @param index     * @return     * @throws Exception     *             select     */    Object get(int index) throws Exception {        rangeCheckOut;        Node temp = first;        int count = 0;        while (temp != null) {            if (count == index) {                return temp.item;            }            count++;            temp = temp.next;        }        return null;    }    /**     * 返回此列表的第一个元素。     *      * @throws Exception     */    Object getFirst() throws Exception {        Node temp = first;        if (temp == null) {            throw new Exception("该集合没有元素");        }        return temp.item;    }    /**     * 返回最后一个元素     *      * @return     * @throws Exception     *      */    Object getLast() throws Exception {        Node temp = last;        if (temp == null) {            throw new Exception("该集合没有元素");        }        return temp.item;    }    /**     * 返回此列表中首次出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。     *      * @param o     * @return     */    public int indexOf {        int count = 0;        Node temp = first;        if (o == null) {            while (temp != null) {                if (null == temp.item) {                    return count;                }                count++;                temp = temp.next;            }        } else {            while (temp != null) {                if (o.equals(temp.item)) {                    return count;                }                count++;                temp = temp.next;            }        }        return -1;    }    /**     *      * 返回此列表中最后出现的指定元素的索引, 如果此列表中不包含该元素,则返回 -1。     */    public int lastIndexOf {        int index = size - 1;        if (null == o) {            for (Node temp = last; temp != null; temp = temp.prev) {                if (null == temp.item) {                    return index;                }                index--;            }        } else {            for (Node temp = last; temp != null; temp = temp.prev) {                if (o.equals(temp.item)) {                    return index;                }                index--;            }        }        return -1;    }    public int size() {        return size;    }    private void rangeCheckOut(int index) throws Exception {        if (index < 0 || index >= size) {            throw new Exception("下标越界" + index);        }    }    /**     * 删除 获取并移除此列表的头。     *      * @throws Exception     */    Object remove() throws Exception {        if (first == null) {            throw new Exception("链表为空");        }        Node oldNode = first;        first = oldNode.next;        if (first != null) {            first.prev = null;        } else {            last = null;        }        size--;        return oldNode.item;    }    /**     * 移除此列表中指定位置处的元素。     *      * @param index     * @throws Exception     */    Object remove(int index) throws Exception {        // 判断长度是否超限        rangeCheckOut;        // 确认要删除的节点        Node oldNode = getIndexNode;        unLinkNode;        return oldNode.item;    }    /**     * remove 从此列表中移除首次出现的指定元素。     */    boolean remove {        // 列表是否有该元素 , 如果有返回该节点        Node oldNode = checkeElement;        if (oldNode != null) {            unLinkNode;            return true;        }        return false;    }    /**     * 移除并返回此列表的第一个元素     *      * @return     * @throws Exception     */    Object removeFirst() throws Exception {        if (first == null) {            throw new Exception("linkedList is null");        }        Object oldValue = first.item;        first = first.next;        if (first == null) {            last = null;        } else {            first.next.prev = null;        }        size--;        return oldValue;    }    /**     * 移除最后一个元素     *      * @return     */    public Object removeLast() {        Node l = last;        if (l == null)            throw new NoSuchElementException();        return unlinkLast;    }    /**     * 将此列表中指定位置的元素替换为指定的元素。     *      * @param index     * @param element     * @return     * @throws Exception     */    public Object set(int index, Object element) throws Exception {        // 判断要插入的索引的位置        rangeCheckOut;        // 获取要插入位置的节点        Node indexNode = getIndexNode;        Object oldValue = indexNode.item;        indexNode.item = element;        return oldValue;    }    /**     * 返回以适当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组     *      * @return     */    public Object[] toArray() {        Object[] result = new Object[size];        int count = 0;        for (Node temp = first; temp != null; temp = temp.next) {            result[count] = temp.item;            count++;        }        return result;    }    private Object unlinkLast {        final Object element = l.item;        Node prev = l.prev;        l.item = null;        l.prev = null; // help GC        last = prev;        if (prev == null) {            first = null;        } else {            last.next = null;        }        size--;        return l.item;    }    private Node checkeElement {        if (o == null) {            // 循环遍历链表            for (Node temp = first; temp != null; temp = temp.next) {                if (null == temp.item) {                    return temp;                }            }        } else {            for (Node temp = first; temp != null; temp = temp.next) {                if (o.equals(temp.item)) {                    return temp;                }            }        }        return null;    }    /**     * 取消链表节点之间的关系     *      * @param oldValue     */    private void unLinkNode(Node oldNode) {        Node beforeNode = oldNode.prev;        Node afterNode = oldNode.next;        if (beforeNode == null) {            // 要删除的节点是头节点            first = afterNode;            afterNode.prev = null;        }        if (afterNode == null) {            // 要删除的节点是尾节点            last = beforeNode;            beforeNode.next = null;        }        if (beforeNode != null && afterNode != null) {            // 删除的非头节点和非尾节点 修改指针的位置            beforeNode.next = afterNode;            afterNode.prev = beforeNode;        }        size--;    }    /**     * 找到要删除的节点     *      * @param index     */    private Node getIndexNode(int index) {        if (index < (size >> 1)) {            // 删除节点的位置为链表的前半段            Node firstNode = first;            for (int i = 0; i < index; i++) {                firstNode = firstNode.next;            }            return firstNode;        } else {            Node lastNode = last;            for (int i = --size; i > index; i--) {                lastNode = last.prev;            }            return lastNode;        }    }    private Object removeAfterNode(int index) {        // 首先迭代        int count = 0;        for (Node temp = first; temp != null; count++) {            if (index == count) {                // 找到要删除的节点进行删除                Object oldValue = temp.item;                Node previous = temp.prev;                Node after = temp.next;                previous.next = after;                size--;                return oldValue;            }            temp = temp.next;        }        return null;    }    /**     * 采用双链表     */    private static class Node<Object> {        Object item;        Node<Object> next; // 下一个节点        Node<Object> prev; // 前驱节点        Node(Node<Object> prev, Object element, Node<Object> next) {            this.item = element;            this.next = next;            this.prev = prev;        }        Node(Object item) {            this.item = item;        }    }}

testCast

/*        LinkedList list = new LinkedList();        list.add;        list.add;        list.add;        list.add;        list.add;        list.add;        list.add;        list.add;        list.add;        list.add;        System.out.println(list.size;    //    System.out.println;        Object first = list.getFirst();        System.out.println("fist=" + first);        Object last = list.getLast();        System.out.println("last=" + ;        int indexOf = list.indexOf;        System.out.println("indexof=" + indexOf);        int lastIndexOf = list.lastIndexOf;        System.out.println("lastIndex=" + lastIndexOf);        LinkedList list2 = new LinkedList();        list2.add;        Object remove = list2.remove();        for (int i=0; i<list.size {            System.out.print("i=" + list.get;        }        Object remove = list.remove;        System.out.println("remove=" + remove);        list.add;        for (int i=0; i<list.size {            System.out.print("i=" + list.get;        }        System.out.println();        list.remove(new Integer;        for (int i=0; i<list.size {            System.out.print("j1=" + list.get;        }        System.out.println();         list.add;         list.add;         list.removeFirst();         list.removeFirst();         System.out.println("------------------");         for (int i=0; i<list.size {                System.out.print("j2=" + list.get;            }    */        LinkedList list2 = new LinkedList();        list2.add(new String("a"));        list2.removeFirst();        list2.add(new String("b"));//        list2.add(new String;    //    list2.remove(new String;        list2.removeLast();        list2.add(new String("c"));        list2.add(new String("d"));        list2.removeLast();    //    list2.removeLast();        list2.add(new String("f"));        list2.set(0, new String("222"));        list2.add(1, new String("14"));        //list2.removeLast();         for (int i=0; i<list2.size();i++) {                System.out.print("j3=" + list2.get + " ");            }        

本文由编程发布,转载请注明来源:LinkedList封装