文档章节

使用数组实现链表--Java

清尘V
 清尘V
发布于 2016/07/26 20:05
字数 1107
阅读 237
收藏 1

声明:基本实现,细节不过多追究。。。

数组需要在创建的时候分配好空间使用,根据索引查询即可;而链表则不需提前分配空间,需要使用的时候动态分配即可。链表中数据的访问是通过指针实现,每个元素都包含下一个元素的一个索引。通过数组实现链表,那么思路如下:

数组中的每个元素是一个对象,包含两个字段:游标和data。

 

第一次初始化时的数据如下:

现在看具体方法:

  • add方法

    public void add(T data) {
        Node node = nodeArray[maxSize - 1];
        int cur = node.getCur();
        int index = 1;
        if (cur == 0) {
            //空数组
        } else {
            while (node.getCur() > 0) {
                node = nodeArray[node.getCur()];
            }
            index = nodeArray[0].getCur();
        }
        //获取要设置数据的节点
        Node currentNode = nodeArray[index];
        //上个节点下个游标为设置数据的节点的索引
        node.setCur(index);
        //备用链表的起始节点的游标改为设置数据节点的游标
        nodeArray[0].setCur(currentNode.getCur());
        //设置游标为0表示链表结束
        currentNode.setCur(0);
        currentNode.setData(data);

        ++length;
    }

  1. 添加数据时,先获取要添加数据的节点的前置节点node
  2. nodeArray[index]则为要设置数据的节点
  3. 将node的游标指向nodeArray[index]
  4. nodeArray[0]的游标指向currentNode的游标指向的节点
  5. 设置currentNode的游标为0表示结尾;设置数据

简单理解:先找到最后一个数据节点(node),然后找到该节点的游标指向的节点(currentNode),nodeArray[0]的游标指向currentNode的游标指向的节点(备用链表),node的游标指向currentNode,currentNode的游标修改为0表示结尾,设置数据。

  • insert方法

    public void insert(int i, T data) {
        Node node = nodeArray[maxSize - 1];
        int j = 0;
        while (node.getCur() > 0 && i> j) {
            node = nodeArray[node.getCur()];
            j++;
        }
        //获取要插入数据的位置
        int cur = nodeArray[0].getCur();

        Node n = nodeArray[cur];
        //设置备用列表指针
        nodeArray[0].setCur(n.getCur());

        n.setCur(node.getCur());
        n.setData(data);

        node.setCur(cur);


        ++length;
    }

 

  1. 先根据索引Index查找到要插入数据的前置节点-node
  2. 根据nodeArray[0]的游标查找到要插入数据的节点n
  3. nodeArray[0]的游标设置为n的游标指向的节点
  4. n的游标设置为node的游标指向的节点,设置数据data
  5. node的游标指向为n
  • delete方法

    public void delete(int i){
        Node node = nodeArray[maxSize - 1];
        int j = 0;
        while (node.getCur() > 0 && i> j) {
            node = nodeArray[node.getCur()];
            j++;
        }
        int cur = node.getCur();
        Node n = nodeArray[cur];

        node.setCur(n.getCur());

        n.setCur(nodeArray[0].getCur());
        nodeArray[0].setCur(cur);

        --j;

    }

  1. 先找到要删除节点的前置节点node
  2. 根据node的游标cur找到要删除的节点n
  3. 设置node的游标指向n的游标指向的节点
  4. 设置n的游标指向nodeArray[0]的游标指向的节点
  5. 设置nodeArray[0]的游标为cur

以上即为通过数组实现的简单链表,完整代码如下:

package com.vincent.array;

/**
 * Vincent 创建于 2016/7/26.
 */
public class LinkedList<T> {

    private int maxSize = Integer.MAX_VALUE;

    private int length = 0;

    private Node[] nodeArray = null;

    public LinkedList() {
        nodeArray = new Node[this.maxSize];
        init();
    }

    public LinkedList(int maxSize) {

        this.maxSize = maxSize;
        nodeArray = new Node[maxSize];
        init();
    }


    private void init() {
        for (int i = 0; i < maxSize; i++) {
            Node node = new Node(i + 1);
            nodeArray[i] = node;
        }
        nodeArray[maxSize - 1].setCur(0);
    }

    public void add(T data) {
        Node node = nodeArray[maxSize - 1];
        int cur = node.getCur();
        int index = 1;
        if (cur == 0) {
            //空数组
        } else {
            while (node.getCur() > 0) {
                node = nodeArray[node.getCur()];
            }
            index = nodeArray[0].getCur();
        }
        //获取要设置数据的节点
        Node currentNode = nodeArray[index];
        //上个节点下个游标为设置数据的节点的索引
        node.setCur(index);
        //备用链表的起始节点的游标改为设置数据节点的游标
        nodeArray[0].setCur(currentNode.getCur());
        //设置游标为0表示链表结束
        currentNode.setCur(0);
        currentNode.setData(data);

        ++length;
    }


    public void insert(int i, T data) {
        Node node = nodeArray[maxSize - 1];
        int j = 0;
        while (node.getCur() > 0 && i> j) {
            node = nodeArray[node.getCur()];
            j++;
        }
        //获取要插入数据的位置
        int cur = nodeArray[0].getCur();

        Node n = nodeArray[cur];
        //设置备用列表指针
        nodeArray[0].setCur(n.getCur());

        n.setCur(node.getCur());
        n.setData(data);

        node.setCur(cur);


        ++length;
    }

    public void delete(int i){
        Node node = nodeArray[maxSize - 1];
        int j = 0;
        while (node.getCur() > 0 && i> j) {
            node = nodeArray[node.getCur()];
            j++;
        }
        int cur = node.getCur();
        Node n = nodeArray[cur];

        node.setCur(n.getCur());

        n.setCur(nodeArray[0].getCur());
        nodeArray[0].setCur(cur);

        --j;

    }

    private class Node<T> {
        private T data;
        private int cur;

        public Node() {
        }

        public Node(int cur) {
            this.cur = cur;
        }

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

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public int getCur() {
            return cur;
        }

        public void setCur(int cur) {
            this.cur = cur;
        }
    }
}

通过数组实现链表加深了两者的理解,数组和链表各有优缺点,在不同条件下选择合适的数据结构有利于提高效率。

© 著作权归作者所有

共有 人打赏支持
清尘V

清尘V

粉丝 41
博文 107
码字总数 47780
作品 0
青岛
程序员
私信 提问
JDK源码之LinkedList

LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实...

村长大神
2014/03/27
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
962
5
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
2018/10/02
0
0
Java数组操作的10大方法

下面是精心整理的Java数组操作的10大方法,大部分代码都来自Stack Overflow。 0、定义一个Java数组 第一种是定义了一个数组,并且指定了数组的长度,我们这里称它为动态定义。 第二种和第三种...

紫魅编程
2016/04/25
313
0

没有更多内容

加载失败,请刷新页面

加载更多

类加载机制过程

1.加载。 将代码转换成字节流加载进内存。加载完之后创建一个Class对象,这个对象是访问数据的入口。 2.验证。 JVM规范验证和代码逻辑验证。 3.准备 内存分配和初始化。对static修饰的类变量...

无精疯
11分钟前
0
0
next.js 提示 chunk styles [mini-css-extract-plugin]

会出现css 导入警告 导入两个插件 并在next.config.js 配置 yarn add webpack-filter-warnings-pluginyarn add mini-css-extract-plugin const FilterWarningsPlugin = require('webpack-......

一箭落旄头
18分钟前
0
0
AWS的自动部署codeploy 应用程序规范文件

codedeploy应用程序的规范文件 ECS平台上的应用规范文件: AppSpec file也可以是 YAML 或 JSON 格式的,可以直接写入控制台内的编辑器内。 AppSpec file用于指定: 用于将流量定向到新任务集...

守护-创造
26分钟前
0
0
Confluence 6 超过当前许可证期限进行升级

这个页面将会对你在进行 Confluence 升级的时候超过了当前许可证的期限进行升级的情况。 许可证警告 在升级的过程中,你将会在 Confluence 的应用程序日志(log file)中看到类似下面的错误提...

honeymoose
32分钟前
0
0
JS 调用Angularjs 的方法

// 1. 获取 Controllerlet appElement = document.querySelector('[data-ng-controller=MessagesCtrl]');let scope = angular.element(appElement).scope();// 2. 调用方法scope.l......

Moks角木
47分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部