What is a linked list in data structures?

Answer 1

A linked list is a finite sequence of nodes each of which contains a pointer field pointing to the next node. In many languages, a pointer to the first node must be supplied. In a simply linked list, the pointer in the last node points to nil. In an empty list, the pointer in the first node points to nil. In the current Java implementation,the types of elements which can be added to the list are those of type Object or one of it's subclasses. In Java, the Object class is the superclass from which all other classes are derived. This makes it possible to add elements of almost any type to a list, except the built in primitive data types (int, long, char, boolean, long,double). To add elements of these types, it is necessary to convert them from primitive types to classes, which Java supports quite easily. In order to convert the primitive types to classes method overloading is used. In Java, there can be multiple definitions of a method with the same name but different parameters. The Java interpreter will know the right method to call while running based on the parameters passed by the caller. This process, method overloading, is employed to convert the different data types listed above. The primary advantage of a linked list over an array is that a linked list can grow and shrink as needed. In Java, the creation of new objects for inclusion in the list is dynamic and can easily be accomplished without much overhead. Other languages,however, pay some overhead for the pointers they utilize. Another advantage of a linked list is the flexibility derived from rearranging elements efficiently, though this flexibility is gained at the expense of quick access to any object in the list.

Answer 2

There are many types of data structures. Arrays and linked lists are the two most commonly used structures. Arrays offer constant-time random-access to any element in the array. This is made possible because array elements are stored in contiguous memory. Given that each element is the same length (in bytes) it is trivial to calculate the address of any element within the array as an offset from the start of the array, where the first element is at offset zero.

The problem with arrays is that elements must be moved around in memory in order to make room for new elements. For that reason, new elements are best placed at the end of the array so that existing elements remain where they are. If there is no room at the end of the array, we can create room by re-allocating the array. Re-allocating memory is a costly operation (impacting performance) but we can minimise that cost by allocating several elements at a time. A naive allocator will double the size of the array on each re-allocation but a more efficient approach is to increase by around 60% on each re-allocation. This naturally means we must keep track of how many elements are "in use" as well as the total number of elements available. Although reasonably efficient, there will be occasions where there is insufficient free memory beyond the end of the array in order to expand into during a re-allocation. When this occurs, the entire array must be moved to a larger block of free memory, and that can prove costly when the array contains large or complex data types, each of which must be copied to the new memory.

Linked lists address some of the issues associated with arrays, but at the expense of constant-time random-access. With linked lists, the data can be stored non-contiguously, thus there is no need to move elements around in memory whenever we add new elements. We simply allocate memory to each new element, independently of all other elements. In order to maintain the actual structure, each data element must be contained in a node, where each node holds a pointer to the next node in the list. In this way it is only necessary to keep track of the first node (the head node). Since the head node is the only node we have constant-time access to, the best place for insertions is at the head of the list, where the new node simply points to the head node and then becomes the head node itself. Inserting anywhere else in the list requires that we traverse the list from node to node to locate the insertion point, placing the new node immediately after that node (the new node points to that node's next node, while that node points to the new node). Although there is a cost in traversing the list to find the insertion point, the cost is (usually) offset by the fact we don't need to move any elements around in memory as we would when inserting into the middle of an array. Thus insertions are generally more efficient.

Extractions are just as efficient as insertions for the same reason.

Linked lists where all insertions and extractions occur at the head are used to implement a stack, a last in first out (LIFO) data structures. With slight modification, keeping track of both the head and the tail of the list, we can create a queue, a first in first out (FIFO) data structure, where insertions occur at the tail and extractions at the head. We can also use linked lists to implement an array that can expand/contract more efficiently, where each node in the list manages a small chunk of the array and new chunks can be allocated without affecting existing chunks. We can also allow bi-directional traversal of the list by holding a second pointer in each node that points back to the previous node in the list (creating a doubly-linked list rather than a singly-linked forward list). We can also create circular linked lists by pointing the tail node "forward" to the head node (normally the tail points to NULL or to a "sentinel" tail node) and by pointing the head node "backwards" to the tail node in a bi-directional list.

Nodes can also be used to create highly complex trees and graphs. For instance, a binary tree can be created using binary nodes that point to the left and right child of the node. For this we need only keep track of the root node, but every node is itself the root of its own sub-tree. Nodes in a tree can also point upwards to their parents, as well as forwards and backwards to their siblings creating linked lists on each level of the tree.