Advantages and disadvantages of single linked list structure and sequential storage structure

Simply compare the single linked list structure with the sequential storage structure :

Single linked list sequence table
The storage allocation mode adopts chain storage structure , A set of arbitrary storage units is used to store the elements of the linear table, and a continuous storage unit is used to store the data elements of the linear table
Time complexity of time performance lookup O(n), Insert and delete on O(1) Time complexity of lookup O(1), Insert and delete elements that need to move half the length of the table on average , Time is O(n)
Space performance does not require pre allocation of storage space , The number of elements is unlimited, and the storage space needs to be allocated in advance , Big waste , Small points are prone to overflow
Through the above comparison, it can be found that :

If the linear table needs to be searched frequently , Rarely when inserting and deleting , Sequential storage structure should be adopted .
If frequent insertion and deletion is required , Single linked list structure should be adopted .

Such as in game development , For user registered personal information , In addition to inserting data during registration , Most cases are read , Therefore, we should consider using sequential storage structure .
And the player's equipment or weapon list in the game , As players play the game , It will be added or deleted at any time , Single linked list structure is more suitable for this situation .
of course , This is a simple analogy , In real software development , The issues to be considered will be much more complex .

When the number of elements in the linear table changes greatly or do not know how much , It is best to use a single linked list structure , In this way, the size of storage space does not need to be considered . And if you know the approximate length of the linear table in advance
, Like a year 12 Months , a week 7 day , This sequential storage structure will be much more efficient .

in short , The sequential storage structure of linear table and the structure of single linked table have their own advantages and disadvantages , We can't simply say which is good and which is bad , According to the actual situation , Comprehensively balance which data structure can better meet and achieve requirements and performance .

©2019-2020 Toolsou All rights reserved,
C++ of string of compare usage Python Study notes ( one )evo Tool usage problems ——Degenerate covariance rank, Umeyama alignment is not possibleRISC-V_GD32VF103-TIMER0 timer interrupt java Array subscript variable _Java Basic grammar : array be based on stm32 Control four-wheel trolley motor drive ( one ) be based on redis Design of liking function Software engineering career planning mysql Query random data by conditions _MySQL Random query of several qualified records centos7 install RabbitMq