黑马程序员技术交流社区

标题: 模仿实现LinkedList(双向链表) [打印本页]

---

作者: 苟苟    时间: 2015-5-1 22:09
标题: 模仿实现LinkedList(双向链表)
模仿实现LinkedList.最先使用了单链表进行模仿.但是每次进行增加和删除操作都要找前驱结点,比较麻烦.
这次使用一个双向链表进行模仿,这样每个结点记录了他的前驱和后继,比较方便. 代码如下:
/**
* <p>Title: DoubleLinkedLinearList.java</p>
* <p>Description: 双向链表(带头节点) </p>
* <p>Copyright: Copyright (c) 2015</p>
* @version 1.0
*/
package com.dt.linearlist;

public class DoubleLinkedLinearList<T> implements ILinearList<T> {

        private Node<T> header;
        private Node<T> pre;
        private int length;
        public DoubleLinkedLinearList(){
                header = new Node<T>();
        }
       
        @Override
        public void destoryList() {
                Node<T> pointer = header.next;
                while(pointer != null){
                        header = null;
                        header = pointer;
                        pointer = header.next;
                }
                length = 0;
        }

        @Override
        public boolean isEmpty() {
                return length == 0;
        }

        @Override
        public int length() {
                System.out.println("length = "+length);
                return length;
        }

        @Override
        public T get(int index) {
                if (!checkBounds(index)) {
                        throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
                }
               
                Node<T> pointer = getElement(index);
               
                return pointer.item;
        }

        @Override
        public boolean add(int index, T t) {
                if (!checkBounds(index)) {
                        throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
                }
                System.out.println("add  "+index+"  "+t.toString());
               
                Node<T> pointer = getElement(index);
                Node<T> node = new Node<T>();
                node.item = t;
               
                node.next = pointer;
                pointer.pre = node;
               
                node.pre = pre;
                pre.next = node;
               
                length++;
                return true;
        }

        @Override
        public T delete(int index) {
                if (!checkBounds(index)) {
                        throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
                }
               
                Node<T> pointer = getElement(index);
               
                pre.next = pointer.next;
                pointer.next.pre = pre;
               
                pointer.next =null;
                pointer.pre = null;
                length--;
                System.out.println("delete  "+index+"  "+pointer.item.toString());
                return pointer.item;
        }

        @Override
        public String traverse() {
                StringBuffer sb = new StringBuffer();
                sb.append("开始遍历单链表");
                sb.append("\n");

                if (header.next == null) {
                        sb.append("单链表无元素");
                        sb.append("\n");
                        sb.append("结束遍历单链表");

                        return sb.toString();
                }

                Node<T> pointer = header.next;
                while (pointer != null) {
                        sb.append(pointer.item.toString());
                        sb.append("\n");
                        pointer = pointer.next;
                }
                sb.append("结束遍历单链表");
                System.out.println(sb.toString());
                return sb.toString();
        }

        @Override
        public boolean add(T t) {
                System.out.println("add  "+t.toString());
                Node<T> pointer = header.next;
                pre = header;
                while(pointer != null){
                        pre = pointer;
                        pointer = pointer.next;
                }
               
                Node<T > node = new Node<T>();
                pre.next = node;
                node.item = t;
                node.pre = pre;
                node.next = null;
                length++;
                return true;
        }

        // 得到指定位置的索引结点.
                private Node<T> getElement(int index) {
                        if (!checkBounds(index)) {
                                throw new ArrayIndexOutOfBoundsException(checkBoundsMsg(index));
                        }

                        int counter = 0;
                        Node<T> pointer = header.next;
                        // 删除index的前一个结点
                        pre = header;
                        while (pointer != null) {
                                if (counter == index) {
                                        break;
                                }
                                counter++;
                                // 未找到对应的索引,继续向下查找
                                pre = pre.next;
                                pointer = pointer.next;
                        }
                        return pointer;
                }

        private String checkBoundsMsg(int index) {
                if (index >= length) {
                        return "下标越界   " + " length: " + length + " index: " + index;
                }
                return null;
        }

        /**
         * 检查指定的索引是否越界
         *
         * @param index
         * @return
         */
        private boolean checkBounds(int index) {
                return index >= 0 && index < length;
        }
       
        private static class Node<T>{
                Node<T> next;
                Node<T> pre;
                T item;
        }
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2