Java教程

手撸代码模拟单向链表--数据结构与算法小结2

本文主要是介绍手撸代码模拟单向链表--数据结构与算法小结2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

正在看文章的你不妨试着回答一下java岗位必问面试题:

1.HashMap的底层数据结构是什么?

2.他的set的过程是怎么样的?

3.hashmap产生哈希冲突了怎么做的?(和问题2有关)

如果你暂时说不清楚的话就试着看下我:

上菜!!!:

本文章脑图:

图片

        前言:不知大家有没有在面试中碰到过这样的问题,反正我是碰到过?而且当时面试的还是一家普通的外包公司,所以hashmap的数据结构相关面试题可以说是非常普遍了,所以关于这一块的数据结构非常有必要花时间去钻研一下,有实力和精力的甚至建议去读源码;

        一    为什么面试官那么喜欢问HashMap这个板块?

很简单!!!

        1.从数据结构的角度:HashMap就涉及到了:数组+链表+红黑树,这对面试者对数据结构的掌握有一定的要求;

        2.从面试检验是否技术底层牢固的角度:死记硬背面试题是可以回答出一些内容的,但是如果没有理解透彻的话,面试官稍微换个角度问,马上就露馅了;

二    学习HashMap底层数据结构小tips

首先每个人有每个人的学习方式,对于像我这种半路出家恶补基础的人来说,我的建议是这样的:

    1.学习数组+链表的数据结构

    2.学习二叉树+红黑树的数据结构

    3.尝试手动依次实现这些数据结构(什么语言随你)

    4.借助HashMap的实现过程,将以上学习到的内容串在一起;

三    什么是链表?

数组很容易理解,先从链表开始)

        3.1    理解链表,建立画面感

        官方定义:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

        大白话:

            1.玩过老鹰抓小鸡吗?被抓的小鸡们就是一个单向链表,除了第一个人(头节点),余下每个人只专注抓稳一个人,后面不管;

图片

2.看过解放军战士的抗洪一线新闻吗?解放军手拉手站在洪水里,和洪水斗争那英勇的样子就是双向链表;

图片

 PS:致敬!!!

3.2    单向链表内部:

            内部的各个节点,每一个节点包含:

                    1.存储的元素(data)

                      2.指向下一个节点的指针next;

public static class Node<T> {
        //存储文件,元素
        private T data;
        //存储下一个节点
        private Node next;
}

整个链表的连接是通过每一个节点内部的next指针指向自己的下一个节点的方式环环相扣,就像老鹰抓小鸡游戏里面的一群小鸡,每一个人只管抓前面一个人,就这样一直保持一个长长的的队伍进行着游戏;

        3.3    双向链表内部:

            双向链表稍微复杂一些,每一个节点包含:

                1.存储的元素(data)

                  2.指向下一个节点的指针next 

                  3.指向上一个节点的指针previous

PS:

 

图片

public static class Node<T> {
        //存储文件,元素
        private T data;
        //存储下一个节点
        private Node next;
        //存储上一个节点
        private Node previous;
}

整个链表的连接是通过每一个节点内部的next指针指向自己的下一个节点,previous指向自己的上一个节点,环环相扣,就像解放军战士手拉着手,铸成最坚固的人墙!!!

四    链表的基本API(查-增-改-删)

先瞅瞅原本方法名是啥样:

import java.util.LinkedList;
//可以直接复制过去自己idea瞅瞅
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        //API 新增
        linkedList.add("one");
        linkedList.add("two");
        System.out.println("linkedList.size() = " + linkedList.size());

        //在头结点增加和在尾结点增加
        linkedList.addFirst("zero");
        linkedList.addLast("ten");

        //修改指定位置的元素
        linkedList.set(1, "changeOne");
        //得到指定位置的元素
        linkedList.get(1);

        //for循环遍历,迭代器使用
        for (String message : linkedList) {
            System.out.println("循环得到" + message);
        }
        System.out.println("------------------------");
        //删除指定位置的元素
        linkedList.remove(1);
        for (String message : linkedList) {
            System.out.println("循环得到" + message);
        }
        System.out.println("------------------------");
        //删除头结点和尾结点:remove() 和removeFirst()作用一样
        //linkedList.remove();
        linkedList.removeFirst();
        //for循环遍历,迭代器使用
        for (String message : linkedList) {
            System.out.println("循环得到" + message);
        }
        linkedList.removeFirst();
        linkedList.removeLast();
    }
}

                也就是要实现下面的这样的方法:

/**
 * 手动模拟一个单向链表list
 * 单向链表API:(这里选择一部分进行实现)
 * 无参构造方法
 * list.add(data)
 * list.add(index,data)
 * list.addFirst()
 * list.addLast()
 * list.remove(index)
 * list.removeAll()
 * list.removeFirst()
 * list.removeLast()
 * list.set(index,data)
 * list.setFirst()
 * list.setLast()
 * list.get(index)
 * list.getFirst()
 * list.getLast()
 */

4.1   查: 链表的查找

        链表的查找操作是比较繁琐的,一句话总结:从头开始一个一个找,直到找到为止,分解如下

        第一步:拿到header节点;

//先定一个node作为标记(当前节点);
Node node = header;

        第二步:   通过header的next指针找到下一个节点;

        第三步:通过第二步拿到的节点,对比当前的index以及目标节点的index,对上了找到然后返回,反之继续获取下一个节点;

//假如index大于等于1,遍历依次将node标记向后移动,一直到index处;
for (int i = 0; i < index; i++) {
    node = node.next;
}
return node;

        第四步:返回node中的data

//获取到对应索引的data
public Object get(int index) {
    return getNode(index).data;
}

        

4.2 增:   链表的指定位置节点的插入(想一下,你想插队老鹰抓小鸡队伍里,你会怎么做?)

        有了第一个get的API,这个就方便一些,步骤如下:

        第一步:获取到指定index-1 处的node(nodeIndexFront)

        第二步:获取到指定index 处的node(indexNode)

        第三步:将第一步的nodeIndexFront的下一个节点设置成新插入的节点

        第四步:将新插入的节点的下一个节点设置成第二步的indexNode

        第五步:链表长度+1

代码上!!!

 

//在指定位置index处,添加data
public void add(int index, T data) {
    //首先判断是否index是否超纲
    if (index < 0 || index > length) {
        throw new IndexOutOfBoundsException("IndexOutOfBoundsException;index超出数组长度");
    }
    //拿到在index处的node
    Node nodeIndex = getNode(index);
    //拿到在index - 1 处的node
    Node nodeIndexFront = getNode(index - 1);
    //将在index - 1 处的node 下一个节点设置为新增的node(nodeInsert)
    Node nodeInsert = new Node(data);
    nodeIndexFront.next = nodeInsert;
    //将在index处的node(nodeInsert)下一个节点设置为原本index处的node
    nodeInsert.next = nodeIndex;
    //长度+1
    length++;
}

4.3 改:   链表的指定位置节点的更改(可以直接看代码)

        到这里,如果你已经理解了前面两个 增+查两个的实现的话,这里就很顺利成章了,步骤如下:

        第一步:获取到指定index-1 处的node(nodeIndexFront)

        第二步:获取到指定index+1 处的node(nodeIndexBack)

        第三步:将第一步的nodeIndexFront下一个节点设置成新插入的节点;

        第四步:将新插入的节点的下一个节点设置成第二步的nodeIndexBack

        第五步:链表长度+1

撸代码:

//修改在index的data
//思路,将index-1处的next设置为新的node,然后
public void set(int index, T data) {
    //首先判断是否超纲(这里可以提取出一个方法,判断index是否越界,越界返回true,否返回false)
    if (index < 0 || index > length) {
        throw new IndexOutOfBoundsException("超出链表节点范围");
    }
    //拿到在index+1处的node
    Node nodeIndexBack = getNode(index + 1);
    //拿到在index - 1 处的node
    Node nodeIndexFront = getNode(index - 1);
    //将在index - 1 处的node 下一个节点设置为新增的node(nodeInsert)
    Node nodeInsert = new Node(data);
    nodeIndexFront.next = nodeInsert;
    //将在index 处的node 下一个节点设置为index+1处的node(nodeIndexBack)
    nodeInsert.next = nodeIndexBack;
}

 4.4 删:这里留个homework吧,自己手动试着实现一下,因为也不难,嘿嘿,皮这一下很开心

//大家可以试着动手实现一下,注意判断index是否越界
public void remove(int index) {
  
}

五    手撸单向链表代码(完整有点长):

public class MyList<T> {
    private Node header;
    private Node tail;
    private int length = 0;

    //无参构造,构造出头节点和尾节点,并且将头节点next指针指向尾节点(头节点不储存元素)
    public MyList() {
        header = new Node<T>();
        tail = new Node<T>();
        header.next = tail;
    }

    /**
     * 新增
     * @param data
     */
    public void add(T data) {
        //构造函数新增node节点
        Node node = new Node(data);
        //如果长度为0,直接在头结点加,并设为尾结点
        if (length == 0) {
            header.next = node;
            //将node设为尾结点
            tail = node;
            length++;
            return;
        }
        //如果长度不为0,将tail的下一个节点设置为node,
        tail.next = node;
        //将node带上tail的标签,变成尾结点
        tail = node;
        //别忘记增加长度
        length++;
    }


    //在指定位置index处,添加data
    public void add(int index, T data) {
        //首先判断是否index是否超纲
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException("IndexOutOfBoundsException;index超出数组长度");
        }
        //拿到在index处的node
        Node nodeIndex = getNode(index);
        //拿到在index - 1 处的node
        Node nodeIndexFront = getNode(index - 1);
        //将在index - 1 处的node 下一个节点设置为新增的node(nodeInsert)
        Node nodeInsert = new Node(data);
        nodeIndexFront.next = nodeInsert;
        //将在index处的node(nodeInsert)下一个节点设置为原本index处的node
        nodeInsert.next = nodeIndex;
        //长度+1
        length++;
    }

    //获取到对应索引的data
    public Object get(int index) {
        /*//return getNode(index).data;代码的分步骤
        Node node = getNode(index);
        Object data = node.data;
        return data;*/
        return getNode(index).data;
    }

    //获取对应位置的节点
    private Node getNode(int index) {
        //首先判断是否超纲
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }

        //先定一个node作为标记(当前节点);
        Node node = header;

        //假如index大于等于1,遍历依次将node标记向后移动,一直到index处;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }


    //修改在index的data
    //思路,将index-1处的next设置为新的node,然后
    public void set(int index, T data) {
        //首先判断是否超纲(这里可以提取出一个方法,判断index是否越界,越界返回true,否返回false)
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }

        //拿到在index+1处的node
        Node nodeIndexBack = getNode(index + 1);
        //拿到在index - 1 处的node
        Node nodeIndexFront = getNode(index - 1);
        //将在index - 1 处的node 下一个节点设置为新增的node(nodeInsert)
        Node nodeInsert = new Node(data);
        nodeIndexFront.next = nodeInsert;
        //将在index 处的node 下一个节点设置为index+1处的node(nodeIndexBack)
        nodeInsert.next = nodeIndexBack;

    }

    //拿到length长度
    public int size() {
        return length;
    }

    //移除index处的data
    //思路就是拿到index - 1和index+1处的node,然后让index+1成为 index-1处的next节点即可
    //大家可以试着动手实现一下
    public void remove(int index) {

    }

    /**
     * 节点
     */
    public static class Node<T> {
        //存储文件,元素
        private T data;
        //存储下一个节点
        private Node next;

        public Node() {
            this.data = null;
        }

        public Node(T data) {
            this.data = data;
        }
    }
}

六    测试方法测试:

public class MyListTest {
    //测试MyList
    public static void main(String[] args) {
        System.out.println("测试新建单向链表");
        MyList<Integer> myList = new MyList<>();
        System.out.println("myList.size() = " + myList.size());

        //增加元素
        System.out.println("测试单向链表增加元素");
        myList.add(0);
        myList.add(1);
        myList.add(2);

        System.out.println("测试单向链表size方法是否准确");
        System.out.println("myList.size() = " + myList.size());

        System.out.println("测试单向链表set方法和get方法是否准确");
        myList.set(2, 9);
        System.out.println("myList.get(2):  " + myList.get(2));

        System.out.println("测试单向链表测试指定位置add元素");
        myList.add(2,8);
        System.out.println("myList.get(2):  " + myList.get(2));
        System.out.println("myList.get(3):  " + myList.get(3));
        System.out.println("myList.size() = " + myList.size());

        //最后留个位置给大家写remove的测试
        //myList.remove();
    }
}

END总结:多问为什么?多思考!多敲代码!不图快,只图啃下来!

完活!这次先到这,以后再慢慢手动实现一下二叉树红黑树啥的~

特此感谢<小灰的算法之旅>这本书,给了很多的启发和系统性的讲解!强烈推荐大家作为算法的入门进行学习;

周末快乐,下周再见,不说了,笨鸟要继续肝算法了~

图片

这篇关于手撸代码模拟单向链表--数据结构与算法小结2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!