Linked List- Intro | Memory Representation | Traversing | Searching | Data Structure & Algorithm

LINKED LISTS

A linked list, or one-way list, is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. That is, each node is divided into two parts: the first part contains the information of the element, and the second part, called the link field or nextpointer field, contains the address of the next node in the list. REPRESENTATION OF LINKED LISTS IN MEMORY Let LIST be a linked list. Then LIST will be maintained in memory, as follows. First of all, LIST requires two linear arrays — we will call them here INFO and LINK — such that INFO[K] and LINK[K] contain, respectively, the information part and the nextpointer field of a node of LIST. LIST also requires a variable name —such as START— which contains the location of the beginning of the list, and a nextpointer sentinel—denoted by NULL—which indicates the end of the list. Since the subscripts of the arrays INFO and LINK will usually be positive, we will choose NULL = 0, unless otherwise stated. TRAVERSING A LINKED LIST Let LIST be a linked list in memory stored in linear arrays INFO and LINK with START pointing to the first element and NULL indicating the end of LIST. Suppose we want to traverse LIST in order to process each node exactly once. This video presents an algorithm that does so and the uses the algorithm in some applications. Our traversing algorithm uses a pointer variable PTR which points to the node that is currently being processed. Accordingly, LINK[PTR] points to the next node to be processed. Thus the assignment PTR = LINK[PTR] moves the pointer to the next node in the list. The details of the algorithm are as follows. Initialize PTR or START. Then process INFO[PTR], the information at the first node. Update PTR by the assignment PTR = LINK[PTR], so that PTR points to the second node. Then process INFO[PTR], the information at the second node. Again update PTR by the assignment PTR = LINK[PTR], and then process INFO[PTR], the information at the third node. And so on. Continue until PTR = NULL. which signals the end of the list. A formal presentation of the algorithm follows. ": Algorithm Traversing a Linked List Let LIST be a linked list in memory. This algorithm traverses LIST, applying an operation PROCESS to each element of LIST. The variable PTR points to the node currently being processed. 1. Set PTR = START [Initializes pointer PTR] 2. Repeat Steps 3 and 4 while PTR != NULL 3. Apply PROCESS to INFO[PTR] 4. Set PTR = LINK[PTR] [PTR now points to the next node] [End of Step 2 loop.] 5. Exit. SEARCHING IN LINKED LIST CASE 1: LIST Is Unsorted Suppose the data in LIST are not necessarily sorted. Then one searches for ITEM in LIST by traversing through the list using a pointer variable PTR and comparing ITEM with the contents INFO[PTR] of each node, one by one, of LIST. Before we update the pointer PTR by PTR = LINK[PTR] we require two tests. First we have to check to see whether we have reached the end of the list; i.e.. first we check to see whether PTR = NULL If not, then we check to see whether INFO[PTR] = ITEM The two tests cannot be performed at the same time. since INFO[PTR] is not defined when PTR = NULL. Accordingly, we use the first test to control the execution of a loop, and we let the second test take place inside the loop. The algorithm follows. Algorithm SEARCH(INFO, LINK, START, ITEM, LOC) LIST is a linked list in memory. This algorithm finds the location LOC of the node where ITEM first appears in LIST or sets LOC = NULL. 1. Set PTR = START 2. Repeat Step 3 while PTR != NULL 3. If ITEM = INFO[PTR], then: Set LOC = PTR, and Exit Else: Set PTR = LINK[PTR] [PTR now points to the next node] [End of If structure] [End of Step 2 loop] 4. [Search is unsuccessful] Set LOC = NULL 5. Exit The complexity of this algorithm is the same as that of the linear search algorithm for linear arrays.

For more details click here