0

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.

Improve this question
14
  • 3
    What are you talking about? Commented Feb 27, 2017 at 20:48
  • I'm talking about this : 2.bp.blogspot.com/-5TR6blbP2Vo/TsLTiKyOH9I/AAAAAAAAAI4/… and a tab, i`m programing in C Commented Feb 27, 2017 at 20:50
  • maybe it's called linked list ?! Commented Feb 27, 2017 at 20:52
  • The things on this image are array and linked list. Commented Feb 27, 2017 at 20:52
  • From that image "link" (haha) you are talking about the difference between using an array and a linked list? Commented Feb 27, 2017 at 20:52

2 Answers 2

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

So you've discussed insertion and accessing, what about searching and deletion?
Searching is related with accessing. And deletion is the opposite of insertion so the same points are applied. Let me add those as well to make it more clear.
1

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.