Storage structure and code implementation of Java linear table

Java data structure learning notes Chapter 1:

There are four basic logical structures for the data after using the program:

Set: there is only a "same set" relationship between data elements. Linear structure: there is a one-to-one relationship between data elements. Tree structure: there is a one-to-many relationship between data elements. Graphical structure or mesh structure: there are many to many relationships between data elements

For different logical structures of data, computers usually have two storage structures on physical disks

Sequential storage structure chain storage structure

This blog post is mainly about linear structure, while linear structure is mainly linear table, and nonlinear structure is mainly tree and graph.

Basic characteristics of linear table:

There is always a unique first data element and a unique last data element. Except for the first data element, each data element in the set has only one predecessor data element. Except for the last data element, each data element in the set has only one successor data element

1. Sequential storage structure of linear table: it refers to using a group of storage units with continuous addresses to store the elements of linear table at one time. In order to use the sequential structure to realize the linear table, the program usually uses the array to save the elements in the linear table. It is a random storage data structure, which is suitable for random access. ArrayList class in Java is an array implementation of linear table.

2. Linear table chain storage structure: any storage unit with a group of addresses will be used to store the data elements in the linear table. The linked list can be divided into:

Single linked list: only one reference is reserved for each node. The reference points to the next node of the current node. No reference points to the head node, and the next reference of the tail node is null. Circular linked list: a linked list connected end to end. Bidirectional linked list: each node has two references, one pointing to the previous node of the current node and the other pointing to the next node of the current node.

The following is the implementation of linear list and bidirectional linked list: LinkedList in Java is a chained implementation of linear list and a bidirectional linked list.

Comparison of two implementations of linear table

Space performance:

Sequential table: the storage space of the sequential table is statically distributed and requires a fixed length array, so some array elements are always wasted.

Linked list: the storage space of the linked list is dynamically distributed, so it will not waste space. However, because the linked list needs more space to save pointers for each node, some space needs to be sacrificed.

Time performance:

Sequential table: the logical order of the elements in the sequential table is consistent with the physical storage order, and supports random access. Therefore, the performance of sequential table is very good when looking up and reading.

Linked list: the linked list uses a chain structure to save the elements in the list, so it has better performance when inserting and deleting elements

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.