Examples of Java simulating single linked list and double ended linked list data structures
Analog single linked list
Linear table: linear table (also known as sequential table) is the most basic, simplest and most commonly used data structure. The relationship between data elements in a linear table is one-to-one, that is, except for the first and last data elements, other data elements are connected from beginning to end. The logical structure of a linear table is simple and easy to implement and operate. In practical applications, linear tables are based on stack , queue, string and other special linear tables. The basic characteristics of linear structure are as follows: 1. There must be a unique "first element" in the set; 2. There must be a unique "last element" in the set; 3. Except for the last element, there is a unique successor (successor); 4. Except the first element, there is a unique precursor (precursor).
Linked list: linked list is a discontinuous and non sequential storage structure on a physical storage unit, The logical order of data elements is realized through the pointer link order in the linked list, and each data item is included in the "chain node" (link). The chain node is an object of a class, which can be called link. There are many similar chain nodes in the chain list. Each link contains a field next that references the next chain node. The chain list object itself stores a reference to the first chain node. First. (if there is no first, it cannot be located) the chain list cannot be like an array (using subscripts) To directly access the data item, you need to locate it by the relationship between the data, that is, access the next chain node referenced by the chain node, and then the next until you access the required data. The time complexity of inserting and deleting at the chain head is O (1), because you only need to change the reference point to find, delete and insert after the specified node, These operations need to search half of the nodes in the linked list on average, and the efficiency is O (n). Single linked list: the linear list is represented by "sequence of nodes". It is called linear linked list (single linked list). It is a data structure of chain access. A group of storage units with arbitrary address are used to store the data elements in the linear list. (this group of storage units can be continuous or discontinuous). The structure of chain nodes:
Data field for storing node values; The pointer field (chain field) next linked list that stores the references of nodes links the N nodes of the linear table together in their logical order through the chain field of each node. The linked list with only one chain field per node is called single linked list. In one direction, there are only references to subsequent nodes
Simulate the double ended linked list to realize the double ended linked list of stack and queue: the double ended linked list is very similar to the traditional linked list Only a new attribute is added, that is, the reference to the last chain node. In this way, it will be very easy to insert at the end of the chain. Just change the next of the rear to the new node without circular search to the last node. Therefore, when insertfirst and insertlast delete the chain head, you only need to change the reference point; When deleting the chain tail, you need to empty the next of the penultimate node, and no reference points to it, so you still need to cycle to read
The stack can be realized by using a linked list, which can be realized by inserting a single linked list. This class is realized by using a double ended linked list:
The linked list queue is realized by double ended linked list: