Do linked lists have any practical uses at all. Many computer science books compare them to arrays and say the main advantage is that they are mutable. However, most languages provide mutable versions of arrays. So do linked lists have any actual uses in the real world, or are they just part of computer science theory?
+2
A:
Yes of course it's useful for many reasons.
Anytime for example that you want efficient insertion and deletion from the list. To find a place of insertion you have an O(N) search, but to do an insertion if you already have the correct position it is O(1).
Also the concepts you learn from working with linked lists help you learn how to make tree based data structures and many other data structures.
Brian R. Bondy
2010-09-23 02:20:52
+2
A:
The main Applications of Linked Lists are
- For representing Polynomials It means in addition/subtraction /multipication.. of two polynomials. Eg:p1=2x^2+3x+7 and p2=3x^3+5x+2 p1+p2=3x^3+2x^2+8x+9
- In Dynamic Memory Management In allocation and releasing memory at runtime. *In Symbol Tables in Balancing paranthesis
- Representing Sparse Matrix
Ref:- http://www.cs.ucf.edu/courses/cop3502h.02/linklist3.pdf
Adi_aks
2010-09-23 02:20:57
Those are some applications, but is representing polynomials really one of the "main" uses for linked lists? I'd say that there are other way more common uses for them, such as regular lists and queues.
Emil H
2010-09-23 02:26:49
+2
A:
They're absolutely precious (in both the popular doubly-linked version and the less-popular, but simpler and faster when applicable!, single-linked version). For example, inserting (or removing) a new item in a specified "random" spot in a "mutable version of an array" (e.g. a std::vector in C++) is O(N) where N is the number of items in the array, because all that follow (on average half of them) must be shifted over, and that's an O(N) operation; in a list, it's O(1), i.e., constant-time, if you already have e.g. the pointer to the "previous" item. Big-O differences like this are absolutely huge -- the difference between a real-world usable and scalable program, and a toy, "homework"-level one!-)
Alex Martelli
2010-09-23 02:21:51
+1
A:
A primary advantage to a linked list as opposed to a vector is that random-insertion time is as simple as decoupling a pair of pointers and recoupling them to the new object (this is of course, slightly more work for a doubly-linked list). A vector, on the other hand generally reorganizes memory space on insertions, causing it to be significantly slower. A list is not as efficient, however, at doing things like adding on the end of the container, due to the necessity to progress all the way through the list.
sleepynate
2010-09-23 02:23:53
Even for singly linked lists, you can keep an end pointer to make it easy to append elements.
Matthew Flaschen
2010-09-23 02:26:07
+1
A:
Linked lists are useful because elements can be efficiently spliced and removed in the middle as others noted. However a downside to linked lists are poor locality of reference. I prefer not using lists for this reason unless I have an explicit need for the capabilities.
seand
2010-09-23 02:24:13
+1
A:
Arrays that grow as needed are always just an illusion, because of the way computer memory works. Under the hood, it's just a continous block of memory that has to be reallocated when enough new elements have been added. Likewise if you remove elements from the array, you'll have to allocate a new block of memory, copy the array and release the previous block to reclaim the unused memory. A linked list allows you to grow and shrink a list of elements without having to reallocate the rest of the list.
Emil H
2010-09-23 02:24:23
+2
A:
Linked lists have many uses. For example, implementing data structures that appear to the end user to be mutable arrays.
If you are using a programming language that provides implementations of various collections, many of those collections will be implemented using linked lists. When programming in those languages, you won't often be implementing a linked list yourself but it might be wise to understand them so you can understand what tradeoffs the libraries you use are making. In other words, the set "just part of computer science theory" contains elements that you just need to know if you are going to write programs that just work.
mattjames
2010-09-23 02:39:37
+1
A:
An Immutable Linked List is the most trivial example of a Persistent Data Structure, which is why it is the standard (and sometimes even only) data structure in many functional languages. Lisp, Scheme, ML, Haskell, Scala, you name it.
Jörg W Mittag
2010-09-23 03:22:53