Detailed explanation of Java data structure (linear table)

Chain storage and implementation of linear list

Another way to realize the linear table is chain storage, that is, those units that store the data elements in the linear table are connected in series with pointers. This method avoids the disadvantage of using continuous cells to store elements in the array, so it is no longer necessary to move elements to make space or fill vacancies when performing insert or delete operations. However, the price we pay for this is that we need to set pointers in each cell to represent the logical relationship between the elements in the table, which increases the overhead of additional storage space

Single linked list

A linked list is a series of cells storing data elements connected in series by pointers. Therefore, each cell has at least two fields. One field is used for the storage of data elements and the other field is a pointer to other cells. A storage unit with one data field and multiple pointer fields is usually called a node

Node Interface

Single linked list node definition

Single linked list implementation of linear table

When using a single linked list to implement a linear list, in order to make the program more concise, we usually add a dummy node in front of the single linked list, also known as the head node. No real data objects are stored in the head node, and its next field points to the node where element 0 in the linear table is located. The introduction of the head node can make some boundary conditions in the operation of the linear table easier to deal with.

Simple test cases

Data structure learning code warehouse:

https://git.oschina.net/wjyonlyone/DataStructure

The above is the whole content of this article. I hope the content of this article can bring some help to your study or work. At the same time, I also hope to support a lot of programming tips!