Linked List Abstract Data Type

Introduction to Linked List ADT

• Linked list consists of a set of data structures known as "nodes"
• Nodes store references to other data structures
• References can be addresses or array indices
• Data structures can be added to or removed from the linked list during execution

Linked Lists vs Arrays and Vectors

• Linked lists can grow and shrink unlike arrays which have a fixed size
• Nodes can be easily inserted between other nodes in a linked list

Node Organization

• A node contains a data field, which can be one or more data fields organized as a structure or object
• A node also contains a pointer that can point to another node

Linked List Organization

• Contains 0 or more nodes
• Contains a head that points to the first node in the list
• The last node points to null, address 0

Empty List

• If a list has 0 nodes, it is an empty list
• In this case the list head points to null

Declaring a Node

• Example code to declare a node:

struct ListNode
{
    int data;
    ListNode *next;
};

• Declaring a node does not allocate memory

Defining a Linked List

• A pointer should be defined for the head of the list
• Example code ListNode *head = nullptr;
• A head point is initialized to nullptr to indicate an empty list

The Null Pointer

• Used to indicate the end of the list
• Always test for a null pointer before using it
• Example code

ListNode* p;
while(!p)

Insertion

• A record is created holding the new item
• The next pointer of the new record is set to link it to the item to follow it in the list
• The next pointer of the item to precede it must be modified to point to the new item

Deletion

• The next pointer of the item immediately preceding the deletion is altered
• The next pointer points to the item following the deleted item

Array versus Linked Lists

• Arrays are better suited for: inserting/deleting at the end, random access, and searching
• Linked Lists are better suited for: Inserting/deleting an element, sequential access, and unpredictable sizes

Types of Lists

• Linear Singly-Linked List
• Circular Linked List: The pointer from the last element points back to the first element
• Doubly Linked List: Pointers exist between adjacent nodes in both directions and the list can be traversed forward or backward

Basic List operations

• Creating a list
• Traversing the list
• Inserting an item in the list
• Deleting an item in the list
• Concatenating two lists into one

List as Abstract Data Type

• Is a data type defined by the user
• More complex than simple data types like int, float, etc
• Implementation details are hidden
• Operations called with functions

Example: Working with Linked List

• The structure of a node

struct stud {
     int roll;
     char name[25];
     int age;
     struct stud *next;
 };

• User defined data type called node

typedef struct stud node;
node *head;

Creating a List

• Create a node (first node) and make the head point to the node

head = (node *) malloc(sizeof(node));

• Steps if there are n nodes in the initial linked list:
• Allocate n records, one by one
• Read in the fields of the records
• Modify the links of the records to form the chain

Traversing the List

• Follow the pointers
• Display the contents of the nodes as traversed
• Stop when the next pointer points to NULL

Inserting a Node

• Insert a node before a specified node
• If the roll value is negative, insert the node at the end of the list
• When a node is added at the beginning, adjust one next pointer
• head is made to point to the new node
• New node points to the previously first element
• When adding at the end, two next pointers must be modified -Last node now points to the new node -New node points to NULL
• When added in the middle, two next pointers are modified -Previous node now points to the new node -New node points to the next node

Deleting a Node

• Required to delete a specified node
• Delete the first node, the last node or an intermediate node