Two-Way List Data Structure PDF
Document Details
Uploaded by BeneficiaryRainforest6697
Tags
Summary
This document provides a detailed explanation of two-way lists, also known as doubly linked lists, including their advantages, disadvantages, and operations, such as searching, deleting, and insertion. The document features illustrations to aid understanding.
Full Transcript
Two-Way List What we have discussed till now is a one-way (singly) list (only one way we can traverse the list) Two-way list (doubly linked list): can be traversed in two direction Forward : From beginning of the list to end Backward: From end to beginning of the list Two-Way List...
Two-Way List What we have discussed till now is a one-way (singly) list (only one way we can traverse the list) Two-way list (doubly linked list): can be traversed in two direction Forward : From beginning of the list to end Backward: From end to beginning of the list Two-Way List Advantages: Can be traversed in either direction (may be essential for some programs) Some operations, such as deletion and inserting before a node, become easier Disadvantages: Requires more space List manipulations are slower (because more links must be changed) Greater chance of having bugs (because more links must be manipulated) Two-Way List A two-way list is a linear collection of data elements called nodes where each node N is divided into three parts: An information field INFO which contains the data of N A forward pointer field FORW which contains the location of the next node in the list A backward pointer field BACK which contains the location of the preceding node in the list List requires two pointer variables: FIRST: which points to the first node in the list LAST: which points to the last node in the list Two-Way List INFO field of node N BACK pointer field of node N FIRST LAST FORW pointer field of node N × × Node N Two-Way List Suppose LOCA and LOCB are the locations of node A and node B respectively in a two-way list. The statement that node B follows node A is equivalent to the statement that node A precedes node B Pointer Property: FORW[LOCA] == LOCB if and only if BACK[LOCB] == LOCA Two-Way List: Node A precedes Node B INFO field of node N BACK pointer field of node N FIRST LAST FORW pointer filed of node N × × Node A Node B FORW[LOCA]==LOCB BACK[LOCB]==LOCA Two-Way List Operations in two-way list Traversing Here it is of no advantage that the data are organized as a two-way list rather than as a one-way list Searching Here the main advantage is that we can search for ITEM in the backward direction if we have reason to suspect that ITEM appears near the end of the list. Deleting Inserting Two-Way List: Deletion Suppose we are given the location LOC of a node N in LIST, and suppose we want to delete N from the list. LOC FIRST LAST Node N (LOC) × × FORW[BACK[LOC]]=FORW[LOC] To the first node of the AVAIL BACK[FORW[LOC]]=BACK[LOC] FORW[LOC]=AVAIL and AVAIL = LOC Two-Way List: Insertion Suppose we are given the location LOCA and LOCB of adjacent nodes A and B in LIST, and suppose we want to insert a given ITEM of information between nodes A and B. LOCA LOCB FIRST LAST Node A Node B × × FORW[LOCA] = NEW NEW FORW[NEW] = LOCB ITEM BACK[LOCB] = NEW and BACK[NEW] = LOCA
