CSE 100/101: Singly-Linked Lists

Linked Lists: A Comprehensive Guide to Understanding In computer science, linked lists are fundamental data structures that are employed to hold data collections. We shall explore linked lists' complexities inthis article, including what they are, how they operate, and the numerousoperations that may be carried out on them. How do Linked Lists work? A linked list is a type of linear data structure made up of several nodes. A key, which can be any type of data, and a pointer, which leads to the next nodein the list, are both contained in each node. The head of the list is the initialnode and serves as the entry point for all of the list's information. The Function of Linked Lists A head pointer, which points to the list's root node, is how linked lists function. This node includes a reference to the following node in the list as wellas some data. Until a node is reached that does not have a pointer to anothernode, this process continues with each node carrying data and a pointer to thenext node. The tail node denotes the conclusion of the list and is referred to assuch. Actions that can be taken with Linked Lists Adding elements to the front or end of the list, returning the front or end elements of the list, removing elements from the front or end of the list, locatingelements in the list, erasing elements from the list, and determining whether thelist is empty are some of the operations that can be done on linked lists.Depending on the size of the list, some of these operations have constant time(O(1)) and others have linear time (O(n)) time complexity. Adding Items to the List's Beginning or End A PushFront action comprises constructing a new node with the key to be added, updating the new node's next pointer to point to the head, and thenupdating the head pointer to link to the newly created node. This process addselements to the front of the list. The constant time complexity of this operationis O. (1). Similar terms like "PushBack operation" or "Append operation" are used to describe adding components to the list's end. This procedure entails searching

for the tail of the list, adding the key to a new node, and updating the tail's nextpointer to point at the new node. The linear time complexity of this operation isO. (n). Returning the List's Front or End Elements A TopFront action, which merely returns the key of the node at the top of the list, returns the front element of the list. The constant time complexity ofthis operation is O. (1). A TopBack action, which entails finding the tail of the list and returning the tail node's key, returns the end element of the list. The linear timecomplexity of this operation is O. (n). Element Removal from the List's Front or End PopFront operations, which entail changing the head pointer to point to the next node in the list and removing the node at the front of the list, are usedto remove the front element of lists. The constant time complexity of thisoperation is O. (1). A PopBack action, which comprises removing the tail node after changing the next pointer of the node preceding the tail to point to null, is usedto remove the last entry of a list. The complexity of this process is linear intime.