Linked list of Java data structure (Java Institute of power nodes)

Single linked list:

Insertfirst: insert a new link point in the header with a time complexity of O (1)

Deletefirst: deletes the link point in the header. The time complexity is O (1)

Find: find the link point containing the specified keyword. Because it needs to traverse the search, it needs to find n / 2 times on average, i.e. o (n)

Remove: delete the link point containing the specified keyword. Because it needs to traverse the search, it needs to search n / 2 times on average, that is, O (n)

Double ended linked list (not bidirectional linked list):

Different from the one-way linked list, it saves a reference to the last link point (last)

Insertfirst: insert a new link point in the header with time complexity O (1)

Insertlast: insert a new link point at the end of the table. The time complexity is O (1)

Deletefirst: deletes the link point in the header. The time complexity is O (1)

Deletelast:: deletes the link point at the end of the table. Since only the link point at the end of the table is saved and the previous link point at the end of the table is not saved (this reflects the advantages of a two-way linked list), when deleting the link point at the end of the table, you need to traverse to find the previous link point at the end of the table. You need to find it n-1 times, that is, O (n) With these methods, a queue can be implemented with a double ended linked list

Ordered linked list:

The data in the linked list is arranged from small to large

On average, the insertion and deletion of a table need to be compared n / 2 times, i.e. o (n), but only O (1) is needed to obtain the minimum data item, because it is always in the header. For the application of frequent operation of the minimum data item, you can consider using an ordered linked list. For example, compared with priority queue and array, the advantage of linked list is that the length is not limited, and when inserting and deleting, There is no need to move data items, so although the time complexity of some operations is the same as that of the array, the actual efficiency is much higher than that of the array. The disadvantage is random access. You can't find a specific data item directly through subscript like array.

The above is the linked list of Java data structures (Java college sorting of power nodes) introduced by Xiaobian. I hope it will be helpful to you. If you have any questions, please leave me a message and Xiaobian will reply to you in time. Thank you very much for your support for the programming tips website!