Arrays and linked lists

Arrays and linked lists are important data structures for every programming language. An array is a sequence of contiguous and ordered elements with a fixed size. The number of elements that can be loaded must be specified during initialization. A linked list is a discontinuous, non-sequential storage structure. The order of data elements is realized through pointer links.

Choosing between arrays and linked lists in your development depends on the scenario and their respective strengths and weaknesses.

Advantages and disadvantages of arrays

For example, if you create a new Object[5], if the first memory address is init_address, the second address is init_address + 1. All array random access is fast, access the first element, with the initial address and subscript can be found, array traversal is also fast. Arrays are fixed in size, which can cause a bit of trouble in element removal and addition. In practical development, array containers are often used, such as Java’s ArrayList, which has a default array size of 10. When the 11th element is added to the arraylist. add method, a new array needs to be created and the elements of the original array need to be copied to the new array. If the ArrayList currently has eight elements, when removing the fifth element, instead of simply setting the fifth element to NULL, move the sixth to eighth elements one bit forward. When the elements of an ArrayList are basic types such as ints, which involve boxing and unboxing, the performance of an ArrayList is slightly worse than using ints directly, but it is sometimes convenient to sacrifice performance.

The pros and cons of linked lists

Linked list elements are linked by Pointers, so their size is unlimited, as long as they don’t explode memory and don’t need to be expanded like an array. It is relatively easy to add and delete a linked list. Take a single linked list as an example. Add an element and place the next pointer of the previous element to a new element. If the list has three elements, when the second element is deleted, the next pointer of the first element points to the third element. List elements are slower to traverse than arrays, and random access to the first element is more cumbersome, requiring traversal.

Linked lists can be divided into single linked lists, bidirectional linked lists and circular linked lists according to their structure.

Singly linked lists:

Bidirectional linked list:

Circular linked lists:

Single linked lists have rings:

In the figure above, there is a single linked list with rings. It should be noted that when using a single linked list, the next pointer of the last element is null as the end of the traversal process, but if the situation as shown in the figure, there will be an infinite loop. For the code implementation of linked lists, not to say much, you can see the LinkedList class in Java, LinkedList implements a bidirectional LinkedList.

The stack and queue

A stack is a linear table with limited operation, allowing only insertion and deletion at one end. The last is first out, the first is last out. For example, if you have a cup that is the size of a coin, you put the coins in the cup one by one, and you can only take the coins out one by one from the top. The coins here are elements of the program, and the cup is the stack.

How to implement a stack?

As mentioned above, arrays and linked lists can be implemented. In an array implementation, for example, the process of pushing (meaning putting an element) is simply put in the index of the array in order, starting with index=0; The array can be accessed from any index element, and the stack can only be accessed from the top, so you need to limit the access to the elements in the array to the largest index in the containing element. Of course, arrays may need to be expanded when the Stack is pressed. Without going into details, the Java Stack class is an example of implementing a Stack.

A queue is also a linear table with limited operations, allowing only delete operations on one end of the table and insert operations on the other end, first-come-first-served. To take a figurative example, there is a pipe the size of a glass ball, placed at an Angle (assuming the left side is high and the right side is low), constantly put balls on the left, the balls will come out on the right, and this pipe can be simply understood as “queue”. Queues can also be implemented using arrays or linked lists.

Stack and queue application scenarios

The stack can be used in a wide range of scenarios. Here are some examples:

  • Browser forward and backward can be used to achieve the stack, a TAB page is a stack, open a network stack, click a link in the web page, that is, forward, and then push the stack, backward corresponding is out of the stack. When the browser creates a new TAB or opens a page in a new TAB, it creates a new stack and pushes open links onto the stack.

  • Android app interface forward and backward, there is an Activity stack, Fragment stack.

  • Function calls can also be implemented on the stack. When entering the called function, a chunk of stack space is allocated to the variables of the function. At the end of the function, the top of the stack is reset, right back into the scope of the calling function.

  • 4 + (6-12 + 2* 2) * 2

The expression is computed as shown below:

There are usually different types of queues, such as circular queues, concurrent queues, blocking queues, etc. Different queues are used in different scenarios.

  • Blocking queue, when the queue is empty, data from the queue head will be blocked until there is data in the queue. If the queue is full, inserting data will also be blocked until there is a free place in the queue before inserting data, and then returning. Blocking queues are usually used in the producer-consumer model, where the production and consumption rates are inconsistent. If the production speed is faster than the consumer can process the data, it may lead to data loss. In this case we can use blocking queues to solve the problem.
  • When there are no idle threads in the thread pool, new tasks request thread resources. The thread pool usually uses queues to store queued requests. Why queue? If the implementation of linked list is used, it can realize the unbounded queue with infinite queuing, but it may lead to too many requests queuing, resulting in slow processing response time. If the array implementation is a bounded queue, when the queue is full, subsequent requests will be rejected. All of these two strategies can be used depending on the scenario.