Sans Pareil Technologies, Inc.

Key To Your Business

Lesson 15 - Linked List


In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. The following are the important terms to understand the concept of Linked List:
  • Node − Each node/link of a linked list can store a data called an element.
  • Next − Each node of a linked list contains a link to the next node called next.
  • LinkedList − A Linked List contains the connection link to the first node called head.

The nodes in a linked list can be stored at random locations in memory unlike arrays or vectors (which are stored in continuous memory segments).

Advantages


  • Linked lists are a dynamic data structure, which can grow and be pruned, allocating and deallocating memory while the program is running.
  • Insertion and deletion node operations are easily implemented in a linked list.
  • Dynamic data structures such as stacks and queues can be implemented using a linked list.
  • There is no need to define an initial size for a Linked list.
  • Items can be added or removed from the middle of list.

Disadvantages


  • They use more memory than arrays because of the storage used by their pointers.
  • Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
  • Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.
  • Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is consumed in allocating space for a back-pointer.

Representation


Linked list can be visualized as a chain of nodes, where every node points to the next node.linked_list
As per the above illustration, the following are the important points to be considered:
  • Linked List contains an element called first.
  • Each link carries a data field(s) and a link field called next.
  • Each link is linked with its next link using its next link.
  • Last link carries a link as null to mark the end of the list.

Types of Linked List


The common types of linked list are:
  • Simple/Single Linked List − Singly linked lists contain nodes which have a data field as well as a 'next' field, which points to the next node in line of nodes. This allow only uni-directional traversal of the list nodes.
  • Doubly Linked List − In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous'). This allows for bi-directional traversal of the list nodes.
  • Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.
  • Multiply linked list — In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data records in a different order (e.g., by name, by department, by date of birth, etc.). While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.

There is also a special implementation of linked list named intrusive list. Intrusive lists do not use a node structure to represent the nodes in a list. They depend upon the data type being stored in the list to provide the previous/next pointers as appropriate. Intrusive lists are very popular in high-performance computing environments where the overhead of allocating a node instance per data item stored is unacceptable.

Sentinel nodes


In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node.

Common Operations


A few common operations supported by linked list implementations:
Insert − Add an element to the list. Elements may be added at the front, back or any random position within the linked list. Inserting into the middle of the list only requires shuffling pointers around and is hence more efficient that inserting into the middle of array/vector.
Delete − Deletes an element from the list. Once again may be at any position within the list. As with insert, only requires shuffling pointers around and does not need to move existing elements into different locations as with array/vector.

Insert Operation


Adding a new node in linked list is a more than one step activity. First create a node using the same structure and find the location where it has to be inserted.
linked_list_insertion_0
Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −
NewNode.next −> RightNode;

linked_list_insertion_1
Now, the next node at the left should point to the new node.
LeftNode.next −> NewNode;
linked_list_insertion_2
This will put the new node in the middle of the two. The new list should look like this −
linked_list_insertion_3
Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Delete Operation


Deletion is also a more than one step process. First locate the target node to be removed
linked_list_deletion_0
The left (previous) node of the target node now should point to the next node of the target node −
LeftNode.next −> TargetNode.next;
linked_list_deletion_1
This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.
TargetNode.next −> NULL;
linked_list_deletion_2
We can keep the deleted node in memory or we can simply deallocate memory and wipe off the target node completely.
linked_list_deletion_3

Reverse Operation


This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.
linked_list_reverse_0
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −
linked_list_reverse_1
We have to make sure that the last node is not the last node. We will have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.
linked_list_reverse_2
Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.
linked_list_reverse_3
We make the head node point to the new first node by using the temp node.
linked_list_reverse_4
The linked list is now reversed.

References


https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm