What is a more efficient implementation of a linked list?

There are at least two ways to present a linked list:

1.) Using representations based on an array of a linked list, where we save std::vectorstructures of type

struct {
    <whatever-type-you-want> item ;
     int   nextitem; 
   }

Here, inserting into the list, does push_back () on the vector and gives the corresponding value for the next element.

2), in which you have a set of structures throughout RAM. Here the insertion is done using C ++ operators new.

Is it right to say that the first method is more efficient, since all elements are in sequential places in memory, because of which it would be possible to create a linked list to a much larger size than the second method

In the second method, there may be memory fragmentation with huge linked lists, due to which it was previously possible to get a segmentation error.

+5
source share
6 answers

I will go against everyone else here and say that, yes, the first approach may be more effective. In the second approach, you allocate memory for a bunch of O (N) times - N is the number of nodes in the list. If you use a vector, you only do the O (log N) number of heap allocations.

, 64- , node , . , nextItem - . 32 64, , 32- ints, 1,5 .

, , , , .

, . , , . , ( nextItem), ( , ).

, , @smilingbuddha , - , , , . , , . node ( - ) . , , , , node.

+4

.


. , .

, , . , .

. , , . - , , , , ..


, ( ) . , , .


, , .

, , , , , / .. , , , ( NumElements * sizeof ( ) ).

std:: deque . , , //.

+3

; , , "" , , , , .

, ; , , , . , , , .

, - . - ; MMU ( ) , , . nextitem int . , , ​​ malloc , .

+2

. , , . , , , .

+1

, , , , , .

, . , , . .

, , . , , , , .

0

# 1, nextitem. , # 2 - , , .

0

All Articles