Data structure sequence table

MoYu-zc 2021-06-24 00:20:00
data structure sequence table


The order sheet

A sequence table is a linear table stored in the memory of a computer in the form of an array , The sequential storage of linear table refers to a group of storage units with continuous addresses , Store the elements in the linear table in turn 、 The data elements that ring on the logical structure in the linear table are stored in the adjacent physical storage units , That is to say, the logical adjacency relationship between data elements is reflected by the adjacency relationship of physical storage of data elements .

1. Implementation sequence table

Code implementation

public class SequenceList<T>{
// Array of storage elements
private T[] list;
// Record the number of elements in the current sequence table
private int n;
public SequenceList(int capacity) {
// Initialize array
this.list = (T[]) new Objects[capacity];
// Initialization length
this.n = 0;
}
// Set a linear table to an empty table
public void clear() {
this.n = 0;
}
// Judge whether the current linear table is empty
public boolean isEmpty() {
return n == 0;
}
// Get the length of the linear table
public int length() {
return n;
}
// Get the element at the specified location
public T get(int i) {
return list[i];
}
// Add elements to the linetype table t
public void insert(T t) {
list[n++] = t;
}
// stay i Insert element at element t
public void insert(int i, T t) {
// Indexes i After the elements , Move backward in turn
for (int index = n; index > i; index--) {
list[index] = list[index - 1];
}
// t Put it in i Index
list[i] = t;
// Element number +1
n++;
}
// Delete the specified location i The element of , And return the element
public T remove(int i) {
// Deleted elements
T current = list[i];
// Indexes i After the elements , Move forward in turn
for (int index = i; index < n - 1; index++) {
list[index] = list[index + 1];
}
// Element number -1
n--;
// Return to delete element
return current;
}
// lookup t Where the element first appeared
public int indexOf(T t) {
for (int i = 0; i < n; i++) {
if (list[i].equals(t)) {
return i;
}
}
return -1;
}
}

Code testing

public class SequenceListTest {
public static void main(String[] args) {
// Create a sequence table object
SequenceList<String> sl = new SequenceList<>(10);
// Test insert
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
sl.insert(1,"test4");
// Test acquisition
String getResult = sl.get(1);
System.out.println(" Get index 1 The result is :"+getResult);
// Test to delete
String removeResult = sl.remove(0);
System.out.println(" The deleted element is :"+removeResult);
// Test empty
sl.clear();
System.out.println(" The number of elements in the cleared linear table is :"+sl.length());
}
}

1

2. Sequence table traversal

1. Inheritance implementation Iterable Interface , rewrite iterator Method ;

2. Provide an inner class SIterator, Realization Iterator Interface , rewrite hasNext Methods and next Method

Code implementation

public class SequenceList<T> implements Iterable<T> {
// ..... Previous code
// rewrite iterator Method
@Override
public Iterator<T> iterator() {
return new SIterator();
}
// Inner method class , Realization Iterator Interface
private class SIterator implements Iterator {
private int cusor;
// Construction method
public SIterator() {
this.cusor = 0;
}
// Does the next one exist
@Override
public boolean hasNext() {
return cusor < n;
}
// Point to the next value
@Override
public Object next() {
return list[cusor++];
}
}
}

Code testing

public static void main(String[] args) {
// Create a sequence table object
SequenceList<String> sl = new SequenceList<>(10);
// Test insert
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
sl.insert(1,"test4");
for (String s : sl) {
System.out.println(s);
}
System.out.println("-------------------------------");
// Test acquisition
String getResult = sl.get(1);
System.out.println(" Get index 1 The result is :"+getResult);
// Test to delete
String removeResult = sl.remove(0);
System.out.println(" The deleted element is :"+removeResult);
// Test empty
sl.clear();
System.out.println(" The number of elements in the cleared linear table is :"+sl.length());
}

2

3. The capacity of the order table is variable

test

  1. Create a capacity of 2 The order of
  2. Insert in 3 Elements
public static void main(String[] args) {
// Create a sequence table object
SequenceList<String> sl = new SequenceList<>(2);
// Test insert
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
}

3

1. When adding elements :
When adding elements , You should check whether the current array size can accommodate new elements , If it can't hold , You need to create a new array with a larger capacity , Let's create an original array here twice as much New array storage elements of capacity .

2. When removing elements :
When removing elements , You should check whether the size of the current array is too large , This will cause a waste of memory space , You should create a smaller array to store elements . If we find that the number of data elements is less than the capacity of the array 1/4, Then create one that is the capacity of the original array 1/2 New array storage elements for .

Code implementation

Modify the above code

// According to the parameters newSize, Reset eles Size
public void resize(int newSize) {
// Define a temporary array , Point to the original array
T[] t = list;
// Create a new array
list = (T[]) new Object[newSize];
// Copy array data
for (int i = 0; i < n; i++) {
list[i] = t[i];
}
}
// Add elements to the linetype table t
public void insert(T t) {
// Judge whether to expand capacity
if (n == list.length) {
resize(2 * n);
}
list[n++] = t;
}
// stay i Insert element at element t
public void insert(int i, T t) {
// Judge whether to expand capacity
if (n == list.length) {
resize(2 * n);
}
// Indexes i After the elements , Move backward in turn
for (int index = n; index > i; index--) {
list[index] = list[index - 1];
}
// t Put it in i Index
list[i] = t;
// Element number +1
n++;
}
// Delete the specified location i The element of , And return the element
public T remove(int i) {
// Deleted elements
T current = list[i];
// Indexes i After the elements , Move forward in turn
for (int index = i; index < n - 1; index++) {
list[index] = list[index + 1];
}
// Element number -1
n--;
// The number of elements is less than 1/4 length , The capacity is reduced to 1/2
if (n < list.length / 4) {
resize(list.length / 2);
}
// Return to delete element
return current;
}

4

4. Time complexity

  • get(i) : It's not hard to see. , Regardless of the number of data elements N How big is the , Only one query is needed to get the corresponding element , So the time complexity is O(1) ;

  • insert(int i,T t) : Every time you insert , All need to put i The element behind the position moves once , With the number of elements N The increase of , The more elements you move , Time is complicated by O(n) ;

  • remove(int i) : Every time you delete , All need to put i The element behind the position moves once , With the amount of data N The increase of , The more elements you move , The time complexity is O(n) ;

Because the bottom layer of the order table is implemented by arrays , The length of the array is fixed , So the container expansion operation is involved in the process of operation . As a result, the time complexity of the sequence table is not linear , At some nodes that need to be expanded , It's going to take a lot of time , Especially the more elements , The more obvious the problem is

版权声明
本文为[MoYu-zc]所创,转载请带上原文链接,感谢
https://javamana.com/2021/06/20210624001910562a.html

  1. Matrix architecture practice of Boshi fund's Internet open platform based on rocketmq
  2. 字节面试,我这样回答Spring中的循环依赖,拿下20k offer!
  3. Byte interview, I answer the circular dependence in spring like this, and get 20K offer!
  4. oracle 11g查看alert日志方法
  5. How to view alert log in Oracle 11g
  6. 手写Spring Config,最终一战,来瞅瞅撒!
  7. Handwritten spring config, the final battle, come and see!
  8. 用纯 JavaScript 撸一个 MVC 框架
  9. Build an MVC framework with pure JavaScript
  10. 使用springBoot实现服务端XML文件的前端界面读写
  11. Using springboot to read and write the front interface of server XML file
  12. 【Javascript + Vue】实现随机生成迷宫图片
  13. [Javascript + Vue] random generation of maze pictures
  14. 大数据入门:Hadoop伪分布式集群环境搭建教程
  15. Introduction to big data: Hadoop pseudo distributed cluster environment building tutorial
  16. 八股文骚套路之Java基础
  17. commons-collections反序列化利用链分析(3)
  18. Java foundation of eight part wensao routine
  19. Analysis of common collections deserialization utilization chain (3)
  20. dubbogo 社区负责人于雨说
  21. Yu Yu, head of dubbogo community, said
  22. dubbogo 社区负责人于雨说
  23. Yu Yu, head of dubbogo community, said
  24. 设计模式 选自《闻缺陷则喜》此书可免费下载
  25. The design pattern is selected from the book "you are happy when you hear defects", which can be downloaded free of charge
  26. xDAI被选为 Swarm 的侧链解决方案,将百倍降低 Swarm 网络Gas费
  27. L2 - 深入理解Arbitrum
  28. Xdai is selected as the side chain solution of swarm, which will reduce the gas cost of swarm network 100 times
  29. L2 - deep understanding of arbitrum
  30. Java全栈方向学习路线
  31. 设计模式学习04(Java实现)——单例模式
  32. Java full stack learning route
  33. Design pattern learning 04 (Java implementation) - singleton pattern
  34. Mybatis学习01:利用mybatis查询数据库
  35. Mybatis learning 01: using mybatis to query database
  36. Java程序员从零开始学Vue(01)- 前端发展史
  37. Java程序员从零开始学Vue(05)- 基础知识快速补充(html、css、js)
  38. Java programmers learn Vue from scratch
  39. Java programmers learn Vue from scratch (05) - quick supplement of basic knowledge (HTML, CSS, JS)
  40. 【Java并发编程实战14】构建自定义同步工具(Building-Custom-Synchronizers)
  41. [Java Concurrent Programming Practice 14] building custom Synchronizers
  42. 【源码分析】- 在SpringBoot中你会使用REST风格处理请求吗?
  43. [source code analysis] - do you use rest style to process requests in springboot?
  44. 框架篇:见识一下linux高性能网络IO+Reactor模型
  45. Framework: see Linux high performance network IO + reactor model
  46. 基础篇:JAVA.Stream函数,优雅的数据流操作
  47. 基础篇:异步编程不会?我教你啊!CompletableFuture(JDK1.8)
  48. Basic part: Java. Stream function, elegant data stream operation
  49. Basic: asynchronous programming won't? I'll teach you! CompletableFuture(JDK1.8)
  50. 技能篇:sed教程-linux命令
  51. 数据库篇:mysql内置函数
  52. Linux 主要的发行系统版本介绍
  53. 网络篇:朋友面试之https认证加密过程
  54. Skills: sed tutorial - Linux command
  55. Database: built in functions of MySQL
  56. Introduction of Linux main distribution system versions
  57. Network: friends interview: the encryption process of HTTPS authentication
  58. [Linux]经典面试题 - 系统管理 - 备份策略
  59. 解决java socket在传输汉字时出现截断导致乱码的问题
  60. [Linux] classic interview questions system management backup strategy