Array versus linked-list

Question

Why would someone want to use a linked-list over an array?

Coding a linked-list is, no doubt, a bit more work than using an array and one may wonder what would justify the additional effort.

I think insertion of new elements is trivial in a linked-list but it's a major chore in an array. Are there other advantages to using a linked list to store a set of data versus storing it in an array?

This question is not a duplicate of this question because the other question is asking specifically about a particular Java class while this question is concerned with the general data structures.

Nina

Related - When to use LinkedList<> over ArrayList<>? - it's Java, but arrays (ArrayList) and linked-lists presumably have the same performance in any language. – Yellowweed

See also: When to use a linked list over an array/array list? – Eidson

@rootTraveller Actually that question would be a duplicate of this question because my question was posted first. – Nina

Answer 1

• It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
• As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.
• Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.
• As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

Prevenient

How are items of different sizes treated any differently? A linked list either uses a fixed struct with a next field (requires fixed size), or stores a pointer to the data in the car (variable size OK). Both approaches are just as easy with a vector. The same for shuffling. – Disguise

No, a linked list can consist of different parts (as long as the next and possible a size is given). – Botulin

I would say shuffling an array is less complicated. – Melchor

@Hugh: I would agree, it could take more memory though, depending on what the array is holding. – Larine

This answer is incorrect and misleading. (except for needing to know an array's size when you declare it) – Duaneduarchy

Wouldn't iterating a linked list be slower because of data locality? – Derte

Yes, I have tested this. Iteration is slightly slower, but not by much. – Hamnet

Although a linked list is slower to search on, it is certainly much lower overhead than an vector. A vector which uses an array under the hood, needs to be recreated/copied in memory when a value is added to the end of its array. It's MUCH more memory intensive than a linked list. However, if you know the size of the data ahead of time and it doesn't grow, then a vector may be best. Depends on the situation, but in general a vector/array is much more intense on a process's memory than a linked list. – Henbit

@Rick, vectors typically overallocate the space they require so that they don't need to allocate new space everytime the size increases. The result is that vectors are typically much less memory intensive, not more then linked lists. – Ryan

@Larine seconded. The way I see it, for an array of anything bigger than two pointers, you're wasting memory and (more importantly in my case) time. – Godfather

What do you mean by foreach context? – Gonyea

The q is Why would someone want to use a linked-list over an array?. How is your last point valid then? Either you imply you lose performance during iteration of arrays, or it's not valid. In fact I see no point other than what OP has already stated – Zackzackariah

Assuming sets of integers, shuffling requires the same memory for both and less operations for the array. Arrays of pointers are just as effective at storing different sized objects as linked lists, which also (in almost all modern implementations) use pointers anyway. Theoretically, you could make a struct based singly linked list, where next is a value instead of a pointer, but the allocation strategy is ridiculous/less maintainable. The stack is a bad place for complex structures so a heap/pointer based LL is almost always the most appropriate, at which point most of your points are wrong. – Testee

@Disguise List is enumeration of homogenous elements. so I agree when u say: A linked list either uses a fixed struct with a next field (requires fixed size). What do you mean by stores a pointer to the data in the car (variable size OK) I did not get you. Can u give the syntax? – Pericles

Can you give an example of the interface for a list that isn't homogeneous? I don't see how a list can store elements of different types while still being a generic container. – Lycanthrope

Vector growth is amortized. You'll perform way way fewer individual allocations with a list than a vector. This overhead will usually dominate the overhead a vector has from moving elements during a reallocation. – Lycanthrope

Because of data locality, there can be a huge performance difference between iterating a list and a vector. Iterating a vector is always faster than iterating a list, even with locality, if only because it requires extra pointer operations. – Lycanthrope

This answer is misleading. 1) You can keep elements of different sizes in an array by keeping pointers to said elements. 2) is the only valid point, linked list is useful when you want pointers to be stable. 3) shuffling array is easier, it can be done by swapping elements 4) you lose performance due to pointer chasing – Rozek

Arrays are not more memory-intensive. Linked list must keep 1 or 2 extra pointers per element, while array keeps only a single pointer to the beginning and size. Dynamically allocated arrays do overallocate memory to amortize insertion complexity though. It is not a problem however. – Rozek

Answer 2

Another good reason is that linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local - affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked list. Even more, it's possible to create lock-free versions using CAS-type operations and avoid heavy-weight locks altogether.

With a linked list, iterators can also traverse the list while modifications are occurring. In the optimistic case where modifications don't collide, iterators can continue without contention.

With an array, any change that modifies the size of the array is likely to require locking a large portion of the array and in fact, it's rare that this is done without a global lock across the whole array so modifications become stop the world affairs.

Precarious

Alex--that's an interesting consideration that would never have occurred to me. Very good answer. I'd upvote you twice if I could. :-) – Nina

Take a look at skip lists (in particular ConcurrentSkipListMap in Java 6) for a good idea of where you can go with this. CSLM is a sorted, concurrent map with excellent performance. Far, far better than a synchronized TreeMap. tech.puredanger.com/2007/10/03/skip-lists – Precarious

…except that ConcurrentSkipListMap or ConcurrentSkipListMap are not lists, even if “List” occurs somewhere in their name. Both require keys that will be sorted and unique. If you need a List, i.e. that data structure that allows duplicate elements in an arbitrary order, that’s not suitable and you would have to go great lengths to make a data structure like LinkedList a concurrently updatable thing. If you only need a concurrent queue or deque, well yes, there are even existing examples, but a concurrent List… I’m not convinced that this is even possible. – Benzaldehyde

Answer 3

Wikipedia has very good section about the differences.

Linked lists have several advantages over arrays. Elements can be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller.

On the other hand, arrays allow random access, while linked lists allow only sequential access to elements. Singly-linked lists, in fact, can only be traversed in one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays is also faster than on linked lists on many machines due to locality of reference and data caches. Linked lists receive almost no benefit from the cache.

Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools.

http://en.wikipedia.org/wiki/Linked_list

Abana

This is the perfect answer. Succinctly describes the advantages and disadvantages of both. – Henbit

thank you)) dead simple but I haven't seen it in wiki) – Standpoint

Answer 4

I'll add another - lists can act as purely functional data structures.

For instance, you can have completely different lists sharing the same end section

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

i.e.:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

without having to copy the data being pointed to by a into b and c.

This is why they are so popular in functional languages, which use immutable variables - prepend and tail operations can occur freely without having to copy the original data - very important features when you're treating data as immutable.

Disguise

Yet another very interesting consideration that I would never have come up with. Thank you. – Nina

How can I do this in python? – Pericles

Answer 5

Besides inserting into the middle of the list being easier - it's also much easier to delete from the middle of a linked list than an array.

But frankly, I've never used a linked list. Whenever I needed fast insertion and deletion, I also needed fast lookup, so I went to a HashSet or a Dictionary.

Archaeological

Very true, insertion and deletion comes after searching most of the time, so need to consider the sum of time complexities as well. – Katekatee

Answer 6

Merging two linked lists (especially two doubly linked lists) is much faster than merging two arrays (assuming the merge is destructive). The former takes O(1), the latter takes O(n).

EDIT: To clarify, I meant "merging" here in the unordered sense, not as in merge sort. Perhaps "concatenating" would have been a better word.

Pathognomy

Only if you're simply appending one list to the other. If you're actually merging two sorted lists then it will take a log more than O(1). – Ferland

@Herms, but you can merge two sorted linked lists without allocating any extra memory, just traversing both lists and setting the pointers appropriately. Merging two arrays would normally take at least one extra array. – Caracal

Yes, merging lists is more memory efficient, but that wasn't really what I was commenting on. Saying merging linked lists is O(1) is very misleading without clarification of the case. – Ferland

@Ferland merging lists is not more memory efficient than merging arrays under any sensible data model. – Marriage

Alexei Averchenko: Concatenating two lists, or even merge-sorting two sorted lists, can be done in place, with O(1) memory. Concatenating two arrays takes O(n) memory necessarily, unless the arrays are already adjacent in memory. I think the point you're aiming at is that where a list of n elements and an array of n elements both take O(n) memory, but the coefficient is higher for linked lists. – Pathognomy

@Pathognomy You’re right, although if the arrays are allocated without any slack, and the lists are not unrolled, then the memory requirements are exactly the same, assuming that both store references. – Marriage

Answer 7

A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.

For example, in a Java environment and using the Eclipse debugger, debugging an ArrayList will reveal a very easy to understand structure:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

On the other hand, watching the contents of a LinkedList and finding specific objects becomes a Expand-The-Tree clicking nightmare, not to mention the cognitive overhead needed to filter out the LinkedList internals:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

Watermark

Answer 8

First of all, in C++ linked-lists shouldn't be much more trouble to work with than an array. You can use the std::list or the boost pointer list for linked lists. The key issues with linked lists vs arrays are extra space required for pointers and terrible random access. You should use a linked list if you

• you don't need random access to the data
• you will be adding/deleting elements, especially in the middle of the list

Arteriosclerosis

Answer 9

For me it is like this,

1. Access

   • Linked Lists allow only sequential access to elements. Thus the algorithmic complexities is order of O(n)
   • Arrays allow random access to its elements and thus the complexity is order of O(1)

2. Storage

   • Linked lists require an extra storage for references. This makes them impractical for lists of small data items such as characters or boolean values.
   • Arrays do not need an extra storage to point to next data item. Each element can be accessed via indexes.

3. Size

   • The size of Linked lists are dynamic by nature.
   • The size of array is restricted to declaration.

4. Insertion/Deletion

   • Elements can be inserted and deleted in linked lists indefinitely.
   • Insertion/Deletion of values in arrays are very expensive. It requires memory reallocation.

Bernitabernj

You have 2 number 2, and 2 number 3 :) – Pronator

We can declare an empty array and then keep adding data as in required. How does it make still a fixed size? – Barbel

@HebleV When you add data to the original array, and if you exceed size, then more memory is allocated and data is appended. Of course, array is mutable but it has a cost of memory allocation, however, linked list doesn't have this cost. Please check: https://mcmap.net/q/10295/-size-of-a-python-list-in-memory – Shack

Answer 10

Two things:

Coding a linked list is, no doubt, a bit more work than using an array and he wondered what would justify the additional effort.

Never code a linked list when using C++. Just use the STL. How hard it is to implement should never be a reason to choose one data structure over another because most are already implemented out there.

As for the actual differences between an array and a linked list, the big thing for me is how you plan on using the structure. I'll use the term vector since that's the term for a resizable array in C++.

Indexing into a linked list is slow because you have to traverse the list to get to the given index, while a vector is contiguous in memory and you can get there using pointer math.

Appending onto the end or the beginning of a linked list is easy, since you only have to update one link, where in a vector you may have to resize and copy the contents over.

Removing an item from a list is easy, since you just have to break a pair of links and then attach them back together. Removing an item from a vector can be either faster or slower, depending if you care about order. Swapping in the last item over top the item you want to remove is faster, while shifting everything after it down is slower but retains ordering.

Depreciation

As I told someone above, I was just trying to relate the question the way it was put to me. I wouldn't ever use an array (or a roll-my-own linked list) in C++ anyway--I'd use the STL versions of both of those. – Nina

Answer 11

Eric Lippert recently had a post on one of the reasons arrays should be used conservatively.

Conquer

Admittedly a good post, but not relevant in a linked list versus array's discussion. – Duaneduarchy

I'd suggest that much of Eric's article is relevant, as it discusses both the disadvantages of arrays and the advantages of Lists, reguardless of the list implementation. – Copaiba

Answer 12

Fast insertion and removal are indeed the best arguments for linked lists. If your structure grows dynamically and constant-time access to any element isn't required (such as dynamic stacks and queues), linked lists are a good choice.

Derte

Answer 13

Arrays Vs Linked List:

1. Array memory allocation will fail sometimes because of fragmented memory.
2. Caching is better in Arrays as all elements are allocated contiguous memory space.
3. Coding is more complex than Arrays.
4. No size constraint on Linked List, unlike Arrays
5. Insertion/Deletion is faster in Linked List and access is faster in Arrays.
6. Linked List better from multi-threading point of view.

Selfimprovement

-1: All of these need to be substantiated, not just enumerated. – Omniumgatherum

Each point has already been explained in above answers. Being a latecomer I had no other option than enumerating. BTW, Which one would you like to be explained? – Selfimprovement

If they've already been explained, then why are you answering? – Omniumgatherum

So that it will give you a summarized view of the discussion. And I like such types of answers so that I don't have to read same explanation again and again. And I did it for those people who have same style of thinking as mine. Different ppl have different styles. Nothing new. – Selfimprovement

Answer 14

Here's a quick one: Removal of items is quicker.

Narcolepsy

Answer 15

Other than adding and remove from the middle of the list, I like linked lists more because they can grow and shrink dynamically.

Aletheaalethia

Vectors (= basically arrays) can do that too and the amortized cost for them is usually smaller than that for lists because of locality-of-reference issues. – Dornick

Answer 16

Linked-list are especially useful when the collection is constantly growing & shrinking. For example, it's hard to imagine trying to implement a Queue (add to the end, remove from the front) using an array -- you'd be spending all your time shifting things down. On the other hand, it's trivial with a linked-list.

Weld

You could have an array-based queue without too much work that was still fast/efficient. You'd just have to keep track of which index was the "head" and which was the "tail". This works fairly well if you need a fixed-size queue (for instance, keyboard buffer in a kernel). – Ferland

And is called a "circular buffer", if you want to look it up in your favourite algorithm reference. – Imbecility

@SteveJessop, That requires you to allocate the worst-case size ahead of time. If you can't do that, you need a linked list based queue. – Alli

Answer 17

No one ever codes their own linked list anymore. That'd be silly. The premise that using a linked list takes more code is just wrong.

These days, building a linked list is just an exercise for students so they can understand the concept. Instead, everyone uses a pre-built list. In C++, based the on the description in our question, that'd probably mean an stl vector (#include <vector> ).

Therefore, choosing a linked list vs an array is entirely about weighing the different characteristics of each structure relative to the needs of your app. Overcoming the additional programming burden should have zero impact on the decision.

Seven

Er..umm.. The std::vector is an array, not a linked-list. The standard linked-list is, well, std::list. – Weld

yeah, but I think vector is a closer to what the op is asking for- a dynamic array replacement. – Seven

@Joel, I was just trying to relate the question as it was put to me by this fellow who's trying to learn C++. I wouldn't bother with coding my own linked list either but that's how he asked me. :-) – Nina

In memory-constrained environments (microcontrollers) for which there are custom compilers, not all of the language (e.g., containers in C++) is implemented. So it may be that you have to code your own linked list. nongnu.org/avr-libc/user-manual/FAQ.html#faq_cplusplus – Teflon

Answer 18

It's really a matter of efficiency, the overhead to insert, remove or move (where you are not simply swapping) elements inside a linked list is minimal, i.e. the operation itself is O(1), verses O(n) for an array. This can make a significant difference if you are operating heavily on a list of data. You chose your data-types based on how you will be operating on them and choose the most efficient for the algorithm you are using.

Cyndycynera

Answer 19

Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.

Larine

Answer 20

1- Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give an initial size of the linked list. Insertion and deletion of nodes are really easier.

2- size of the linked list can increase or decrease at run time so there is no memory wastage. In the case of the array, there is a lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements is wasted. There is no such problem in the linked list as memory is allocated only when required.

3- Data structures such as stack and queues can be easily implemented using linked list.

Spell

1 and 2 are solved by allocating array dynamically. 3. Stack can be implemented as array just as easily. Queues are a bit more complicated, but not too hard - you can make a circular buffer. – Rozek

Answer 21

Linked List are more of an overhead to maintain than array, it also requires additional memory storage all these points are agreed. But there are a few things which array cant do. In many cases suppose you want an array of length 10^9 you can't get it because getting one continous memory location has to be there. Linked list could be a saviour here.

Suppose you want to store multiple things with data then they can be easily extended in the linked list.

STL containers usually have linked list implementation behind the scene.

Hamrick

Answer 22

Linked List

Its more preferable when it comes about insertion! Basically what is does is that it deals with the pointer

1 -> 3 -> 4

Insert (2)

1........3......4
.....2

Finally

1 -> 2 -> 3 -> 4

One arrow from the 2 points at 3 and the arrow of 1 points at 2

Simple!

But from Array

| 1 | 3 | 4 |

Insert (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Well anyone can visualize the difference! Just for 4 index we are performing 3 steps

What if the array length is one million then? Is array efficient? The answer is NO! :)

The same thing goes for deletion! In Linked List we can simply use the pointer and nullify the element and next in the object class! But for array, we need to perform shiftLeft()

Hope that helps! :)

Roxanneroxburgh

Answer 23

In an array you have the privilege of accessing any element in O(1) time. So its suitable for operations like Binary search Quick sort, etc. Linked list on the other hand is suitable for insertion deletion as its in O(1) time. Both has advantages as well as disadvantages and to prefer one over the other boils down to what you want to implement.

-- Bigger question is can we have a hybrid of both. Something like what python and perl implement as lists.

Mexican

Answer 24

Suppose you have an ordered set, which you also want to modify by adding and removing elements. Further, you need ability to retain a reference to an element in such a way that later you can get a previous or next element. For example, a to-do list or set of paragraphs in a book.

First we should note that if you want to retain references to objects outside of the set itself, you will likely end up storing pointers in the array, rather than storing objects themselves. Otherwise you will not be able to insert into array - if objects are embedded into the array they will move during insertions and any pointers to them will become invalid. Same is true for array indexes.

Your first problem, as you have noted yourself, is insertion - linked list allows inserting in O(1), but an array would generally require O(n). This problem can be partially overcome - it is possible to create a data structure that gives array-like by-ordinal access interface where both reading and writing are, at worst, logarithmic.

Your second, and more severe problem is that given an element finding next element is O(n). If the set was not modified you could retain the index of the element as the reference instead of the pointer thus making find-next an O(1) operation, but as it is all you have is a pointer to the object itself and no way to determine its current index in the array other than by scanning the entire "array". This is an insurmountable problem for arrays - even if you can optimized insertions, there is nothing you can do to optimize find-next type operation.

Equanimity

Could you please elaborate this: "it is possible to create a data structure that gives array-like by-ordinal access interface where both reading and writing are, at worst, logarithmic." – Pronator

There's some stuff on Wikipedia under Dynamic Array / Vriants section. It's not quite what I had in mind, though... Imagine a b+tree like structure with pages but no keys, instead each intermediate page remembers how many elements are there in each of sub-pages, while the leaf pages just hold the elements in a small array. When inserting an element into a leaf page you have to move ~half the page to make room, then go up and update item count on all ancestor pages. When looking up an element #N, simply add up subordinate page item count until you cross N, and then descend into that subtree – Equanimity

Answer 25

as arrays are static in nature, therefore all operations like memory allocation occur at the time of compilation only. So processor has to put less effort at its runtime .

Berardo

Answer 26

Only reason to use linked list is that insert the element is easy (removing also).

Disadvatige could be that pointers take a lot of space.

And about that coding is harder: Usually you don't need code linked list (or only once) they are included in STL and it is not so complicated if you still have to do it.

Anthia

Pointers take a lot of space? Not really. If you're storing a linked list of booleans, then sure, percentage wise the pointers take a lot of space. But if you're storing complex objects (which is generally the case) then the pointers would probably be negligible. – Ferland

forgot smile :) But did say 'could' not 'is'. – Anthia

Answer 27

Besides convenience in insertions and deletions, the memory representation of linked list is different than the arrays. There is no restriction on the number of elements in a linked list, while in the arrays, you have to specify the total number of elements. Check this article.

Duggins

Answer 28

Why would someone want to use a linked-list over an array?

This is only one reason - if you need a linked list data structure and a programming language you are using is not supports a pointers.

Portraiture

Answer 29

While many of you have touched upon major adv./dis of linked list vs array, most of the comparisons are how one is better/ worse than the other.Eg. you can do random access in array but not possible in linked list and others. However, this is assuming link lists and array are going to be applied in a similar application. However a correct answer should be how link list would be preferred over array and vice-versa in a particular application deployment. Suppose you want to implement a dictionary application, what would you use ? Array : mmm it would allow easy retrieval through binary search and other search algo .. but lets think how link list can be better..Say you want to search "Blob" in dictionary. Would it make sense to have a link list of A->B->C->D---->Z and then each list element also pointing to an array or another list of all words starting with that letter ..

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Now is the above approach better or a flat array of [Adam,Apple,Banana,Blob,Cat,Cave] ? Would it even be possible with array ? So a major advantage of link list is you can have an element not just pointing to the next element but also to some other link list/array/ heap/ or any other memory location. Array is a one flat contigous memory sliced into blocks size of the element it is going to store.. Link list on the other hand is a chunks of non-contigous memory units (can be any size and can store anything) and pointing to each other the way you want. Similarly lets say you are making a USB drive. Now would you like files to be saved as any array or as a link list ? I think you get the idea what I am pointing to :)

Six

Answer 30

Why a linked list over an array ? Well as some have already said, greater speed of insertions and deletions.

But maybe we don't have to live with the limits of either, and get the best of both, at the same time... eh ?

For array deletions, you can use a 'Deleted' byte, to represent the fact that a row has been deleted, thus reorging the array is no longer necessary. To ease the burden of insertions, or rapidly changing data, use a linked list for that. Then when referring to them, have your logic first search one, then the other. Thus, using them in combination gives you the best of both.

If you have a really large array, you could combine it with another, much smaller array or linked list where the smaller one hold thes 20, 50, 100 most recently used items. If the one needed is not in the shorter linked list or array, you go to the large array. If found there, you can then add it to the smaller linked list/array on the presumption that 'things most recently used are most likey to be re-used' ( and yes, possibly bumping the least recently used item from the list ). Which is true in many cases and solved a problem I had to tackle in an .ASP security permissions checking module, with ease, elegance, and impressive speed.

Equiponderance

Answer 31

Depending on your language, some of these disadvantages and advantages could be considered:

C Programming Language: When using a linked list (through struct pointers typically), special consideration must be made sure that you are not leaking memory. As was mentioned earlier, linked lists are easy to shuffle, because all were doing is changing pointers, but are we going to remember to free everything?

Java: Java has an automatic garbage collect, so leaking memory won't be an issue, but hidden from the high level programmer is the implementation details of what a linked list is. Methods such as removing a node from the middle of the list is more complicated of a procedure than some users of the language would expect it to be.

Bachelor

Answer 32

i also think that link list is more better than arrays. because we do traversing in link list but not in arrays

Irmgardirmina

Answer 33

The difference between an array and a linked list is that an array is an index based data structure, every element is associated with an index whereas the linked list is a data structure that uses references, each node is referred to another node. In array size is fixed whereas in link list size is not fixed.

Windlass

Answer 34

People using linklist must read. People will fall in love with array again. It talks about Out Of Order exeuction,hardware prefetch, memory latency etc.

http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html

Itch

This presumes that there is a one-size fits all answer indicating that one is always better than the other, and that's simply not the case. The analysis of each case and the skill of the developer are vital components in selecting the proper tool for a given job. – Endogen

Sorry for a late reply, but I am the authod of the referenced article. Absolutely agreed with David. there are no black and white answer, but my point in this article was to show things wrong with linked list that aren't usually considered. – Newmarket