University Data Structures: Insertion and Removal in Linked Lists

This assignment provides a comprehensive overview of linked lists, focusing on the fundamental operations of insertion and removal of data. It begins by defining the abstract data type (ADT) and explaining how data is stored using nodes and pointers within a linked list structure. The assignment details the process of inserting and removing data at the beginning of the list and at arbitrary positions, including relevant code examples to illustrate these operations. It also covers the deletion of nodes at specific positions. Furthermore, the assignment contrasts linked lists with alternative data structures, specifically arrays, highlighting the differences in memory allocation, cache locality, and access methods. The references at the end of the assignment provide additional resources for further study on data structures and algorithms.

Running head: DATA STRUCTURE
SELECTED TOPIC: EXPLAIN HOW TO INSERT AND REMOVE ITEMS FROM A
LINKED LIST
Name of Student
Name of University
Author note

1DATA STRUCTURE
Data next Data NullData Next
nexnextnext
addres
adaddress
Data next
List abstract data type
An abstract data type is a data type whose implementation is kept hidden from the front-
end user while it is used in operations. In data structures abstraction is widely used and one of
them is list abstract data type (List ADT). These lists can be referenced as containers of data’s
which keeps data abstracted to the end users and deals with data structures (Lafore 2017). The
best example of list abstract data type is linked list.
Storage of the list values in a linked list
In linked list, one need to create a structure which has memory allocation for data and
links, each of this structure is called as node. This links are used as pointers which points to the
next node. These linked nodes as a whole is called a linked list (Lam 2015).
In order to insert a data in the linked list, one need to create a node, link the last node of
the current list with this new node and terminate the link part of the last node to null. In this
process the linked list stores the list values. In the process of storing data’s in linked list, one may
have to traverse the entire list (Mehlhorn 2013).

2DATA STRUCTURE
Insertion and removal of data at the starting node
In order to insert a data at the start of the linked list, one needs to add the node containing
the specified data at the very beginning of the linked list. Firstly, the existence the current linked
list is checked by checking the value of the head node, if the head node is null then the linked list
is empty and by creating the temp node the very first node of the of the list is created.
In case the head node already exists the new or temp node’s data part contains the data to be
added, and the link of the temp node contains the address of the head node or the first node the
current linked list. In this data’s at the starting of a linked list is added. Following code explains
this in details:
CODE:
voidadd_element(struct node **hd)
{
intnum;
struct node *t1 = NULL, *t2 = NULL;
printf("Enter the element to be added: ");
scanf("%d", &num);
if(*hd == NULL)
{
*hd = (struct node *)malloc(sizeof(struct node));

3DATA STRUCTURE
(*hd)->data=num;
(*hd)->next=NULL;
}
else
{
t2=(struct node *)malloc(sizeof(struct node));
t2->data=num;
t2->next=(*hd);
}
}
In this code, *hd represents the head node of the given linked list, the malloc command is used
for memory allocation and t2 represents the temp node which contains the new data.
Deletion of data is done by eliminating a particular node. By making the second node as the head
node and eliminating the link of the first node with the second node and then eliminating the
node itself (Cash et al. 2014). This can be explained in detail in the following code.
CODE:
voiddelete(struct node **hd)
{

4DATA STRUCTURE
struct node *t1=NULL;
t1=(*hd);
(*hd)=(*hd->next);
t1->next=NULL;
t1=NULL;
}
Insertion or removal of data at an arbitrary index in the linked list
In order to insert a data in an arbitrary position in the linked list one need to traverse to the node
after which the data is to be added then a new node containing the new data is added and the
linked list is continued after that. The preceding node is linked to the new node and the
succeeding node is linked with the new node, in this manner, a new node is added in between.
This can be explained in details in the following code.
CODE:
voidadd_element(struct node **hd)
{
intnum, position;
struct node *t1=NULL, *t2=NULL;
printf("Enter the element to be added: ");

5DATA STRUCTURE
scanf("%d", &num);
if(*hd==NULL)
{
*hd=(struct node *)malloc(sizeof(struct node));
(*hd)->data=num;
(*hd)->next=NULL;
}
else
{
t1 = (struct node *)malloc(sizeof(struct node)) ;
t2=(*hd);
t1->data=num;
t1->next=NULL;
for(inti=1;i<position-1 && t2!=null;i++)
{
t2=t2->next;
}

6DATA STRUCTURE
t1->next=t2->next;
t2->next=t1;
}
}
In the code above, t1 is the new node and t2 is the referencing node that is used to traverse to the
preceding node.
Deletion of data at nth position can be done by asking for the data which is to be deleted. The
next step is to check each node’s data while traversing, and if found, the node’s link with the
succeeding node is eliminated and then the preceding node is linked with the succeeding node, in
the process the desired node gets eliminated (Kang et al. 2015). This is explained in the
following code.
CODE:
void delete(struct node **hd)
{
int k;
printf("Enter the element to be deleted:\n");
scanf("%d", &k);
struct node *t1=NULL, *t2=NULL;

7DATA STRUCTURE
t2=*hd;
while(t2->data!=k)
{
t1=t2;
t2=t2->next;
}
t1->next=t2->next;
}
In the above code, t2 is the desired node to be eliminated. While doing t1->next=t2->next, the
preceding node is linked with the succeeding node.
An alternative list data structure
An alternative type of data structures that can be used is array. In array the data is stored
in a process called continuous memory allocation (Berztiss 2014). The very structure of array is
different than that of linked list. Array provides with better cache locality compared to linked
list. In array data structure one can access the data randomly unlike linked list also array is
considered to be less complicated.

8DATA STRUCTURE
References
Berztiss, A.T., 2014. Data structures: theory and practice. Academic press.
Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.C. and Steiner, M., 2014,
February. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and
Implementation. In NDSS (Vol. 14, pp. 23-26).
Kang, J., Hur, C.K., Mansky, W., Garbuzov, D., Zdancewic, S. and Vafeiadis, V., 2015, June. A
formal C memory model supporting integer-pointer casts. In ACM SIGPLAN Notices(Vol. 50,
No. 6, pp. 326-335). ACM.
Lafore, R., 2017. Data structures and algorithms in Java. Sams Publishing.
Lam, M., 2015. Data structures and Algorithms.
Mehlhorn, K., 2013. Data structures and algorithms 1: Sorting and searching (Vol. 1). Springer
Science & Business Media.