Where are Linked lists used ?

[Kakashi Hatake]

I wanted to know the applications of linked lists in real-world applications. Are there any alternatives to Linked lists ?

Thanks so much ^_^

[swinefish]

Linked lists end up in a huge range of different application - anywhere you need to store a large number of objects, but don't know exactly how many items you need - as such, you can't really use an array. C# has a List<T> class which allows you to build lists of any type. As far as I know this uses a linked list implementation. I use List<T> all the time, as do a number of people I know.

As a general rule, you won't need to code your own linked list - most languages have it implemented. But it is very useful in more applications than I could possibly name.

Keep well,
M

[griswolf]

Data structures have several properties that are important:

1. basic size
2. size is fixed or variable
3. incremental size per item
4. length/size complexity
5. add/append complexity
6. search complexity
7. remove/delete complexity
8. iteration direction

Linked lists come in two flavors: Singly linked list and doubly linked lists.

For simple singly linked lists:

1. basic size is approximately 2 pointers (plus optional 'size' element)
2. size is variable
3. incremental size is "one pointer" (plus the size of the stored object)
4. length/size complexity is
   • if no 'size' saved: O(n)
   • if 'size' saved: O(1)
5. add/append complexity is O(1) (added cost if 'size' is maintained)
6. search complexity is O(n)
7. remove/delete is (added cost if 'size' is maintained)
   • if you have a 'pointer' to the node before the removed node: O(1)
   • if you only have a 'pointer' to the removed node: O(n)
8. iteration direction is forward only

For doubly linked lists

1. basic size is approximately 3 pointers (plus optional 'size' element)
2. size is variable
3. incremental size is "two pointers" (plus the size of the stored object)
4. length/size complexity is
   • if no 'size' saved: O(n)
   • if 'size' saved: O(1)
5. add/append complexity is O(1) (added cost if 'size' is maintained)
6. search complexity is O(n)
7. remove/delete is O(1) if you have a 'pointer' to the removed node (added cost if 'size' is maintained)
8. iteration direction is forward or backward

Lists are very useful for holding data that is always accessed 'in order' rather than needing to look for a particular item.

Lists are very useful for holding many items where you need to add or remove items during the course of the program.

Lists are not best for random access (choose arrays or vectors) or access by key (choose a dictionary or map).

If you know the number of items, lists are more expensive in both time and space than an array or vector.

If you only ever need to access items from front to back, and if you never need to delete any item except the front one, singly linked lists beat doubly linked lists.

If you ever need to 'go backward' from an item, or if you need to delete "here" in the middle of a list, then doubly linked lists beat singly linked lists.

Real world applications abound. For instance:
a list of the lines in a file
a list of the options in a menu (particularly if you can drag menu items around)
a list in the GPS of the turns along your route

There are many alternatives to lists. Search for 'Data Structures' online, or read any good programming book. Briefly (and, I'm sure, incompletely) here are some well known, often used data structures

• lists: linear access, variable size
  • singly linked
  • doubly linked
  • (view as) stack
  • (view as) queue
• arrays: indexed access, fixed size
  • (view as) vector
  • (view as) stack
  • (view as) queue
• hashes: key access, size constraint depends on implementation
  • set (given an item, find if it is in the set)
  • map (given a key, find the value)
• trees: structured access (from root node 'outward'), variable size sometimes log(n) search
  • binary tree (each node has two daughters)
  • b-tree (each node has many daughters), guaranteed balanced, ordered
  • balanced tree / red-black tree (balanced binary tree)
• graphs: each node is related to some set of other nodes Often implemented as a list of outbound (and optionally inbound) arcs in each node.