How to insert and remove items from a Linked List.
The list ADT has certain variables of the same type and is also arranged numerical order, these will only run certain operations. This doesn’t mean that the certain objects are in numerical order, it just means that each object has a position in the List, starting with zero. The following operations are get, insert, remove, remove at, replace, size, is empty and is full. The list ADT is mutable which means changes can be done but not all ADT’s have mutable functionalities. The list is also an interface, which would mean that different classes can provide the actual implementation of this data type. The specific classes include ArrayList and LinkedList. This ADT can solve problems such as developers using too much time for inserting and deleting variables, when the data of the list dynamically grows, not accessing random elements from the list and inserting elements to any position.
As a Linked List has multiple node elements that are linked together using pointers, it allows the elements to be stored in different locations allowing for a more optimal storage of information. In a singly linked list, each node in the list stores the data and a pointer to the next node in the list, it does not store any pointer to the previous node. To store a single linked list, only the pointer to the first node in that list must be stored. The last node in a single linked list points to nothing. All nodes are allocated space in the memory randomly.
There are 4 things needed to insert a value at the start of a Singly Linked List. The first one is allocate the node, then put in the data, then make next of new node as head and last of all move the head to point to the new node. Below is an example of doing the above function, first I have created a class and then I made a function that will print the list, then made a function that will add the value at the start of the list. Last of all, I have collated all functions to run the code.
There are 3 steps needed to remove a value from an arbitrary index at any place in the Singly Linked List. The first one is find the previous node of the node to be deleted. The second one is change the next of previous node. The last step is free the memory for the node to be deleted. Below is an example of doing the above function, first I have created a class, then I made a function that will keep adding a value at the start of the list. The next function will remove a specific node and then will print the nodes, last of all it will run the code.
Linked List and Array List are two different implementations of the List data structure. Array List can randomly access data fast, so it can find any element in constant time. But adding or removing a value other than the end will require elements to be moved and will need more memory to provide space. Linked List can allow users to use constant time inserting and removing using iterators, but only sequential access to the elements. But finding a position in the list takes time proportional to the size of the list. Linked Lists can be dynamic in size, and have more optimal insertion and deletion than arrays. In addition, extra memory space is required for each pointer within the Linked List. The main benefits of using a Linked List are when repeating existing iterators to insert and remove elements. Another benefit of using a Linked List is when we add or remove from the head of the list. One of the major benefit of Array List is by default it will assign default size as 10. Another benefit is that you can add different types’ of objects in to the Array List.
References:
https://dsaa.werp.site/post/the-linked-list-data-structure/
http://careerdrill.com/blog/coding-interview/choosing-the-right-data-structure-to-solve-problems/
https://medium.com/@govinda_raj/arraylist-vs-linkedlist-f8c5099153b5
Liam's Blog 