Use of memory between an array and a linked list

Question

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.

I'm talking about this : http://2.bp.blogspot.com/-5TR6blbP2Vo/TsLTiKyOH9I/AAAAAAAAAI4/biElxcl2svQ/s1600/liste.jpg and a tab, i`m programing in C — , Feb 27 '17 at 20:50
From that image "link" (haha) you are talking about the difference between using an array and a linked list? — Weather Vane, Feb 27 '17 at 20:52
Sorry ! I corrected my question. I really though it a tab in English... I`'m not only learning C but also English ;) — , Feb 27 '17 at 20:54
Arrays are contiguous (so that chunks of data are placed sort of in a queue), but linked lists can have their data scattered across memory, which, of course, doesn't help to make improve the speed when you iterate through them. But one can insert data inside a linked list relatively faster then one would do with an array. The same goes for adding data to the end/beginning of the list. — ForceBru, Feb 27 '17 at 20:57
the program will stock coordinates from a given file and then use then in order to create pixel in an image — , Feb 27 '17 at 20:58
@f42, if you're going to use the data in order, you should probably use an array due to reasons I explained in my previous comment. — ForceBru, Feb 27 '17 at 21:00
I'll use it in order. And if I don't know the number of int I need is it still better to use an array or not ? Because I'll need to copy it every time — , Feb 27 '17 at 21:02
my general rule is to use dynamic memory only for the following reasons: 1) The memory must persist outside of the current function 2) you don't know how much you will need until runtime 3) you need "a lot" of it (depends on the stack size for your system). If none of those are true, then use an array instead of a linked list. — yano, Feb 27 '17 at 21:17
@f42: Don't think in terms of "which is more efficient" - think in terms of "which will make the code easier to write, understand, and debug". Having said that, if you're doing image processing, then you want to use arrays. Most image processing algorithms rely on the image data being contiguous in memory (that is, all in the same sequence). — John Bode, Feb 27 '17 at 21:35

score 1 · Accepted Answer · edited Feb 28 '17 at 01:00

Both link list and array have good and bad sides.

Array

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.
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.
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.
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)
Memory must be contiguous, which can be a problem on old x86 machines with 64k segments.
Freeing is a single operation.

LinkList

Accessing at a particular position take O(n) time, because you have to traverse the entire list to get to a particular position.
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.
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)
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]
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.
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.

So you've discussed insertion and accessing, what about searching and deletion? — RoadRunner, Feb 27 '17 at 23:14
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. — Ayon Nahiyan, Feb 27 '17 at 23:19

score 1 · Answer 2 · answered Feb 27 '17 at 23:23

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.

Use of memory between an array and a linked list

2 Answers2