手写双向链表LinkedList的几个常用功能

布满荆棘的人生 2022-03-06 03:54 173阅读 0赞

实现的功能如下：  
1）创建链表  
2）添加节点（默认添加和指定位置添加）  
3）访问某一个节点  
4）删除节点  
5）获得链表的长度大小  
6）判断链表是否为空  
7）自定义链表的打印格式  
8）清空链表

**\*注意：要弄清楚节点的前赴 和 后继，删除时要注意赋值的顺序！！！**

定义 链表中 节点的类Node

public class Node {
        
        /**
         * 值
         * 
         */
        Object value;
        
        /**
         * 前驱
         */
        Node pre;
        
        /**
         * 后继
         */
        Node next;
        
        public Node(){
            
        }
        
        public Node(Object value, Node pre, Node next) {
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
    }

定义双向链表LinkList，实现功能如下：

/**
     * 双向链表
     * 
     * @author min
     *
     */
    public class LinkList {
    
        /**
         * 头结点
         */
        private Node head;
        
        /**
         * 尾结点
         */
        private Node tail;
        
        private int size;
        
        public LinkList() {
            head = new Node();
            tail = new Node();
            
            head.next = tail;
            tail.pre = head;
            size = 0;
            
        }
        
        public int size() {
            return size;
        }
        
        public boolean isEmpty() {
            return size==0;
        }
        
        public void clear() {
            head.next = tail;
            tail.pre = head;
            size = 0;
        }
        
        /**
         * 在末尾添加新的数据
         * 
         * @param value 数据
         */
        public void add(Object value) {
            Node node = new Node(value,tail.pre,tail);
            tail.pre.next = node;
            tail.pre = node;
            size ++;
            }
        
        /**
         * 在特地位置创建新的节点
         * @param index
         * @param value
         */
        public void add(int index, Object value) {
            checkLinkList(index);
            
            if(index == size -1) {
                //插在最后一位
                add(value);
            }
            else{
                Node x = node(index-1);
                Node y = node(index);
                Node node = new Node(value, x, y);
                x.next = node;
                y.pre = node;
                size ++;
            }        
        }
        
        /**
         * 获取特定位置的节点
         * @param index
         * @return 节点存储的值
         */
        public Object get(int index) {
            //检查是否在链表内
            checkLinkList(index);
            //节点的值
            return node(index).value;
        }
    
        /**
         * 删除特定的节点
         * @param index
         * @return 被删除的节点
         */
        public Node remove(int index) {
            checkLinkList(index);
            Node x = node(index);
            x.pre.next = x.next;
            x.next.pre = x.pre;
            size --;
            return x;
        }
        
    
        /**
         * 检查索引是否在链表内
         * 
         * @param index
         */
        private void checkLinkList(int index) {
            if(index > size() ||index < 0)
                throw new ArrayIndexOutOfBoundsException(index);
        }
    
        /**
         * 遍历链表查询特定的节点
         * 
         * @param index 索引
         * @return 指定的节点
         */
        private Node node(int index) {
            //第1个节点
            Node firstNode = head;
            //最后1个节点
            Node lastNode = tail;
            
            //从头开始遍历
            if(index <=(size>>1) ) {
                Node indexNode = firstNode;
                for(int i = -1; i < index; i++)
                    indexNode = indexNode.next;
                return indexNode;
            }
                
            //从尾遍历
            else{            
                Node indexNode = lastNode;
                for(int i = size; i>index; i--) {
                    indexNode = indexNode.pre;
                }
                return indexNode;
            }        
        }
        
        /**
         * 重写链表输出方式
         * 
         */
        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            String str = "";
            for(int i = 0; i<size; i++) {
                str = String.valueOf(i + ":"+ node(i).value + "\n");
                builder.append(str);
            }
            return builder.toString();
        }    
    }

测试  
![图片描述][1241833022-5c7780962c300_articlex]

--------------------

只实现了一些常用功能，自己写的和工具包中的类对比，会从中get到很多。受益多多~

[1241833022-5c7780962c300_articlex]: /images/20220306/c06c96fe295844769201df3a1c7904b9.png