Algorithms & Data Structures - Linked List

Objectives
At the end of the class you should be able to answer:

Explain the design, use, and operation of a linear list

Implement a linear list using a linked list structure

Understand the operation of the linear list ADT

Write application programs using the linear list ADT

Design and implement different link-list structures

Basic Operations
The four basic list operations are :

1. Insertion
2. Deletion
3. Retrieval
4. Traversal

Insertion

• Insertion is used to add a new element to the list.
• List insertion can be ordered or random.
• Ordered list are maintained in sequence according to the data or, when available, a key that identifies the data.
• In random lists there is no sequential relationship between two elements.Random lists are sometimes called chronological lists.

Figure 5-1 Shows the insertion of data into a list



Deletion

• Deletion is used to remove an element from the list.
• Deletion from a list requires that the list be searched to locate the data being deleted
• Once located, the data are removed from the list.

Figure 5-2 Shows the Deletion operation


Retrieval

• Retrieval is used to get the information related to an element without changing the structure of the list.
• List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

Figure 5-3 Shows retrieving data from a list



Traversal

• List traversal processes each element in a list in sequence
• It requires a looping algorithm rather than a search.

Implementation

• Several data structures can be used to implement a list; we use a linked list.
• Linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list.

Data Structure
To implement a list, we need two different structures, a head node and data node.


Figure 5-5 Shows a head node and data node



Algorithm
Create List:
Create list allocate the head structure and initializes the metadata for the list.
Figure 5-6 shows the header before and after it is initialized by create list.


Figure 5-6 Create list



Algorithm for creating a list



Insert Node
Insert node adds data to a list. Given the predecessor, there are three steps to the insertion:
1. Allocate memory for the new node and move data to the node.
2. Point the new node to its successor.
3. Point the new node’s predecessor to the new node.


Figure 5-7 Add node to empty list



Insert at Beginning

• To insert a node at the beginning of the list, we simply point the new node to the first node of the list and then ser the head pointer to point to the new first node.
• Figure 5-8 shows inserting a node at the beginning

Figure 5-8 Shows Add node at Beginning



Insert in Middle

• To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node.
  
• Figure 5-9 shows inserting a node in the middle.
  

Figure 5-9 Add node in Middle



Insert at End

• To add at the end of the list, we only need to point the predessor to the new node.
  
• The Figure5-10 insert the node at the end
  

Figure 5-10 Add node at End



Algorithm for Insertion is shown in figure 5-2



Delete Node

• The delete node algorithm logically removes a node from the list by changing various link pointers and then physically delete the node from dynamic memory.
  
• Figure 5-11 shows Deleting the first node
  

Delete First Node



Algorithm for Deleting a node


Retrieve Node
Figure 5-5 Shows retrieve list node algorithm








Advance Linked List

• Circular Linked List
  
• Circular linked list is a type of linked list where the last node will point back to the first node
  

Graphical view of a circular linked list