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).
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));
(*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
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: “);
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
t2=t2->next;
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;
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.
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.
