Generalized Lists or Multilists: Notion, Structure, and Operations - Prof. Saumendra Sengu, Study notes of Data Structures and Algorithms

Download Generalized Lists or Multilists: Notion, Structure, and Operations - Prof. Saumendra Sengu and more Study notes Data Structures and Algorithms in PDF only on Docsity! Notion of Generalized Lists or Multilists for structures. Every structure of interest can be seen as an example of a generalized list. We propose that a list is (a partially ordered collection of items) * either an empty list () (also known as a Null list) * or a list comprising of atoms and/or lists. e.g. L = () is a Null list. L = (a b c) is a list with three atoms appearing as indicated. L = (A B) where A and B themselves are lists. K = (a (b c) () (d e f) g) is a list with 5 elements. The 2nd, the 3rd and the 4th items are lists. ■ Lists with no sublists are Linear lists or chains. ■Note that every generalized list L can be drawn as a multiway tree where there is precisely one path from the root of the tree to a specific node of the tree. Some operations on a generalized list are on a list L: a. car L -> yields the first item of the list if the latter is not empty. b. cdr L -> yields the resultant list after removal of the first item of the list given that the latter is not empty. e.g. Given that L = ((a b) () d) car L = (a b) cdr L = (() d) If K = (()), car K = () and cdr K = () However, car cdr (K) is an error. c. One could insert an item into a list using cons operator as shown. If L = (a b c d) cons (x L) = (x a b c d) item is inserted at the left. Thus, cons (x ()) yields the list (x). Note that cons operator always produces a list. A list L = (a b c d) appears as The list L = ((a b) (c (d e))) appears as a b c d