Linear tables of Java data Structures -Java Things Column

In this article, we will talk about one of the most important data structures in Java — linear tables. Again, the linear tables correspond to the List in the following figure.

The contents in the red box are the large family of linear lists, and the yellow part is important to understand. The elements in a linear list are arranged in a linear order (linear here means logical). Linear lists are divided into two categories, namely sequential lists and linked lists:

First, sequence table

The data elements in a sequential table are stored contiguously, and the memory partitions are contiguous. The storage structure is shown as follows:

Our ArrayList is an array implementation at the bottom, and the elements are ordered in memory. An ArrayList is a representation of a sequential list in Java.

Second, the linked list

Linked lists are usually stored in a discontinuous, non-sequential manner in physical storage, and the logical order of data elements is realized through references in the list.

1. One-way linked lists

Very simply, objects in memory are randomly distributed, and not only do objects store data such as Joe and Joe, they also hold a next reference to the next object to determine the logical order of a set of objects.

Circular linked lists

Very simple, just like a one-way list, except the next of the last object points to the first object.

3. Bidirectional linked lists

It holds not only a next reference to the next object, but also a prev reference to the previous object.

It’s important to remember the bidirectional LinkedList diagram, and in the next article we’ll talk about LinkedList implementation as a bidirectional LinkedList.

Stack and queue

Stack and queue are two special types of linear tables.

1, stack

A stack is a linear table with limited operations. The limitation is that additions and deletions are only allowed at the end of the linear table, which is called the top of the stack and the bottom of the stack. Adding new elements to a stack is called pushing, and removing elements is also called pushing.

As shown in the figure above, putting Zhao Liu into the stack is called pressing the stack. Without putting Zhao Liu into the stack, removing Wang Wu directly is called out of the stack. Only the elements can be added and deleted from the top of the stack. The Stack shown in the first figure of this article is the implementation of a Stack in Java. For example, the dishes that are washed last are stacked on top of each other, but they are taken from the top every time they are used, so the dishes that are washed first are not easily used.

2, the queue

A queue is also a linear table with limited operations. Elements can only be removed (removed) from the header, and elements can be added from the end of the queue, which is called the header.

If you look at the diagram above, you can only add elements from the end of the queue and remove (delete) elements from the head of the queue. The Queue in the first figure of this article is a representation of queues, which are based on linked lists. Note that Queue is an interface and writing the following code directly will cause an error

Queue queue = new Queue(); Queue is an interface and cannot be instantiatedCopy the code

The correct usage is

Queue queue = new LinkedList(); // The correct usage is based on linked listsCopy the code

The LinkedList implementation of queues is implemented by subclass LinkedList. The Queue interface reduces access to the LinkedList, providing only operations from the end of the Queue to the head of the Queue.

And just to impress you, I’ll give you an example, which is a little gross, but I’ll make sure you remember that when you’re drinking a beer, you go to the bathroom and pee normally, and that’s called an example. The process of drinking too much and throwing up is called stack.

The above is the introduction of Java linear tables, interviews will often be asked about, the follow-up article will focus on all said, I hope to help you.

Previous: The difference between Arraylist and Vector – Java Things column

Next: To be continued