Shulou(Shulou.com)05/31 Report--

This article mainly introduces "what is a linear table". In daily operation, I believe many people have doubts about what is a linear table. I have consulted all kinds of data and sorted out simple and easy operation methods. I hope it will help you answer the doubts about "what is a linear table"! Next, please follow the small series to learn together!

preface

Through the previous data structure and algorithm basics, I know some of the concepts and importance of data structure, so today we summarize the content related to the linear table. Of course, I share my understanding with you. (ps Do you have any confusion about whether it is a node or a node?)

In fact, to be honest, many people may still be confused about the difference and connection between linear tables, sequential tables, and linked lists!

Linear table: logical structure, that is, the relationship between exposed data, do not care how to achieve the underlying, the logical structure of the data structure is a large classification of linear structure and nonlinear structure, and sequential tables, linked lists are a linear table.

Sequence list, linked list: physical structure, he is to implement a structure on the actual physical address. For example, the order table is implemented in arrays. A linked list does most of the work with pointers. Different structures differ in different scenes.

In Java, everyone knows the List interface type, which is a logical structure because it is a series of methods and data that encapsulate a linear relationship. And the concrete realization is actually related to the physical structure of the content. For example, the contents of a sequence table are stored using arrays, and then a get, set, add method is done based on arrays, while a linked list is based on pointers. When we consider data relationships in objects, we must consider properties of pointers. Pointing and value of pointer.

The following diagram illustrates the relationship between linear tables. It may be a bit imprecise, but you can refer to it and use it as an example later.

Linear Table Basic Architecture

For a linear table. Regardless of its specific implementation, their method function names and implementation effects should be consistent (i.e., the same method is used to achieve the same logical effect, and the difference is operational efficiency). The concept of linear tables is somewhat similar to Java interfaces/abstract classes. The most famous are ArrayList and LinkedList, List is a logical structure, indicating that this structure is a linear table, while ArrayList and LinkedList are more of a physical structure (arrays and linked lists).

So based on object-oriented programming thinking, we can write a linear table as an interface, and the specific implementation of the order table and linked list of classes can achieve this linear table method, improve the readability of the program, there is one more important point, remember the beginner data structure and algorithm when the linear table is a fixed type (int), with the progress of knowledge, we should use generics to achieve more reasonable. The specific design of the interface is as follows:

package LinerList; public interface ListInterface { void Init(int initsize);//initialize table int length(); boolean isEmpty();//is empty int ElemIndex(T t);//Find number getElem(int index) throws Exception;//Get data according to index void add(int index,T t) throws Exception;//insert data according to index void delete(int index) throws Exception; void add(T t) throws Exception;//tail insert void set(int index,T t) throws Exception; String toString();//convert to String output }

sequence table

Sequential tables are array based implementations, so all implementations need to be array based. For a sequential table structure there should be an array of data and a valid length.

Also note that the size of the initialization array, you can fix the size, but the author will double it for availability if there is not enough memory.

The following focuses on some concepts and methods that beginners are easy to confuse.

insert operation

add(int index,T t)

Where index is the number position of insertion, t is the inserted data, and the insertion process is:

(1)Move one bit backward from last (last bit with data) forward to index to make room for index position

(2)Assign the data to be inserted to the index position to complete the insertion operation.

It can be seen that if the sequence table is very long, if the insertion efficiency is relatively low (insertion time complexity is O(n)), if frequent insertion is high, the complexity is quite high.

delete operation

Similarly, deletion is also very resource-intensive. The principle is similar to insertion. The operation of deleting the index position is to assign the data to the previous position in sequence starting from index+1. For details, see this figure:

code implementation

Here I implement a sequence table for you to learn as a reference:

package LinerList; public class seqlist implements ListInterface { private Object[] date;//array stores data private int lenth; public seqlist() {//initial size defaults to 10 Init(10); } public void Init(int initsize) {//initialize this.date=new Object[initsize]; lenth=0; } public int length() { return this.lenth; } public boolean isEmpty() {//is empty if(this.lenth==0) return true; return false; } /* * * @param t * Returns equal results,-1 is false */ public int ElemIndex(T t) { // TODO Auto-generated method stub for(int i=0;i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.