手写实现单向链表

太过爱你忘了你带给我的痛 2022-11-14 10:09 165阅读 0赞

上篇我们分析了链表的相关原理，今天我们手动实现一个单向链表：

1、定义一个内部类节点：

/**
     * 链表节点的内部类
     */
    class Node{
        T data;
        Node next;
        public Node(T data,Node node){
            this.data = data;
            this.next = node;
        }
    }

2、基本参数的定义：

Node list;//成员变量
    
    int size;//链表节点的个数
    //构造方法
    public NandaoLinkedList(){
        size = 0;
    }

3、首节点添加数据

/**
     * 头部添加节点
     * @param data
     */
    public void put(T data){
        Node cur = new Node(data,list);
        list = cur;
        size ++;
    }

4、指定位置添加数据

/**
     * 在指定位置插入节点数据
     * @param index
     * @param data
     */
    public void put(int index,T data){
        Node head = list;
        Node cur = list;
        for(int i = 0; i < index;i++){
            head = cur;
            cur = cur.next;
        }
        cur = new Node(data,cur);
        head.next = cur;
        size++;
    }

5、删除头部节点：

/**
     * 删除头部节点
     * @return
     */
    public T remove(){
        if (list != null) {
            Node head = list;
            list = head.next;
            head.next = null;
            size--;
        }
        return null;
    }

6、删除指定位置的节点：

/**
         * 删除指定位置的数据
         * @param index
         * @return
         */
        public T remove(int index){
            checkPositionIndex(index);
            if(index == 0){//首节点删除
                remove();
            }else {
                Node head = list;
                Node cur = list;
                for(int i=0;i<index;i++){
                    head = cur;
                    cur = cur.next;
                }
                head.next = cur.next;
                cur.next = null;
                size--;
            }
            return null;
        }

7、删除未节点：

/**
     * 删除未节点
     * @return
     */
    public T removeLast(){
        Node head = list;
        Node cur = list;
        if(list != null){
            while (cur.next != null){
                head = cur;
                cur = cur.next;
            }
            head.next = null;
            size--;
        }
        return null;
    }

8、修改指定节点：

/**
     * 修改指定节点
     * @param index
     * @param newData
     * @return
     */
    public T setNode(int index,T newData){
        checkPositionIndex(index);
        Node cur = list;
        for(int i=0;i<index;i++){
            cur = cur.next;
        }
        cur.data = newData;
        return null;
    }

9、获取首节点数据：

/**
     * 获取头节点数据
     * @return
     */
    public T get(){
        if(list != null){
            return list.data;
        }else {
            return null;
        }
    }

10、查询指定位置参数：

/**
     * 查询指定位置参数
     * @param index
     * @return
     */
    public T get(int index){
        checkPositionIndex(index);
        Node cur = list;
        for(int i=0;i<index;i++){
            cur = cur.next;
        }
        return cur.data;
    }

11、链表节点是否越界的验证

/**
     * 链表节点是否越界的验证
     * @param index
     */
    public void checkPositionIndex(int index) {
        if(!(index>=0 && index <= size)){
            throw new IndexOutOfBoundsException("传的位置参数不在此链表范围之内！");
        }
    }

12、测试方法

@Override
    public String toString() {
        Node node = list;
        System.out.println("结果为：");
        for(int i=0;i < size;i ++){
            System.out.print(node.data+ " ");
            node = node.next;
        }
        System.out.println("结束了！");
        return super.toString();
    }
    
    public static void main(String[] args) {
        NandaoLinkedList<Integer> linkedList = new NandaoLinkedList();
    
        linkedList.put(12);
        linkedList.put(2);
        linkedList.put(3);
        linkedList.put(4);
        linkedList.put(5);
        linkedList.put(6);
    
       // linkedList.put(2,2);
    
        //linkedList.remove();
      //  linkedList.remove(0);
       /// linkedList.removeLast();
        //linkedList.setNode(1,1);
      //  Integer integer = linkedList.get();
        Integer integer = linkedList.get(15);
        System.out.println("查询结果："+integer);
    
    
        //String s = linkedList.toString();
        //System.out.println("返回值："+ s );
    }

13、执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

main里有各种测试数据，大家可以详细测试一下，会受益颇多！

到此，手写单向链表分析完成，下篇我们用单向链表实现LRU算法功能，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/237c0d85c2124ee8af01b3abd98ed500.png