CODEWITHSUNDEEP
cmemory-management
user7586561
user7586561

Reputation:

Use of memory between an array and a linked list

In C, which is more efficient in terms of memory management, a linked list or an array?

For my program, I could use one or both of them. I would like to take this point into consideration before starting.

Upvotes: 0

Views: 158

Answers (2)

Ayon Nahiyan
Ayon Nahiyan

Reputation: 2200

Both link list and array have good and bad sides.

Array

  1. Accessing at a particular position take O(1) time, because memory initialized is consecutive for array. So if address of first position is A, then address of 5th element if A+4.

  2. If you want to insert a number at some position it will take O(n) time. Because you have to shift every single numbers after that particular position and also increase size of array.

  3. About searching an element. Considering the array is sorted. you can do a binary search and accessing each position is O(1). So you do the search in order of binary search. In case the array is not sorted you have to traverse the entire array so O(n) time.

  4. Deletion its the exact opposite of insertion. You have to left shift all the numbers starting from the place where you deleted it. You might also need to recrete the array for memory efficiency. So O(n)

  5. Memory must be contiguous, which can be a problem on old x86 machines with 64k segments.

  6. Freeing is a single operation.

LinkList

  1. Accessing at a particular position take O(n) time, because you have to traverse the entire list to get to a particular position.

  2. If you want to insert a number at some position and you have a pointer at that position already, it will take O(1) time to insert the new value.

  3. About searching an element. No matter how the numbers are arranged you have to traverse the numbers from front to back one by one to find your particular number. So its always O(n)

  4. about deletion its the exact opposite of insertion. If you know the position already by some pointer suppose the list was like this . p->q->r you want to delete q all you need is set next of p to r. and nothing else. So O(1) [Given you know pointer to p]

  5. Memory is dispersed. With a naive implementation, that can be bad of cache coherency, and overall take can be high because the memory allocation system has overhead for each node. However careful programming can get round this problem.

  6. Deletion requires a separate call for each node, however again careful programming can get round this problem.

So depending on what kind of problem you are solving you have to choose one of the two.

Upvotes: 1

Havenard
Havenard

Reputation: 27874

Linked list uses more memory, from both the linked list itself and inside the memory manager due to the fact you are allocating many individual blocks of memory.

That does not mean it is less efficient at all, depending on what you are doing.

While a linked list uses more memory, adding or removing elements from it is very efficient, as it doesn't require moving data around at all, while resizing a dynamic array means you have to allocate a whole new area in memory to fit the new and modified array with items added/removed. You can also sort a linked list without moving it's data.

On the other hand, arrays can be substantially faster to iterate due to caching, path prediction etc, as the data is placed sequentially in memory.

Which one is better for you will really depend on the application.

Upvotes: 1

Related Questions