Chapter: Programming and Data Structures - Linear Data structures- List

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

List ADT array-based implementation

List Abstract Data Type - List ADT array-based implementation

LIST ADT ARRAY-BASED IMPLEMENTATION

List Abstract Data Type

 

A list is a sequence of zero or more elements of a given type a1, a2,..., an (0)

n        :  length of the list

a1       :         first element of the list

an       :         last element of the list

n = 0 :         empty list

 

elements can be linearly ordered according to their position in the list

 

 

 

We say ai precedes ai + 1, ai + 1 follows ai, and ai is at position i

Let us assume the following:

 

L       :         list of objects of type element type

x        :         an object of this type

p       :         of type position

END(L)       :         a function that returns the position following the

 

last position in the list L

 

Define the following operations:

 

1.Insert (x, p, L)

Insert x at position p in list L

If p = END(L), insert x at the end

 

If L does not have position p, result is undefined

 

2. Locate (x, L)

returns position of x on L

returns END(L) if x does not appear

 

3.Retrieve (p, L)

returns element at position p on L

 

undefined if p does not exist or p = END(L)

 

4.Delete (p, L)

delete element at position p in L

undefined if p = END(L) or does not exist

 

5.Next (p, L)

returns the position immediately following position p

 

6.Prev (p, L)

returns the position previous to p

 

7.Makenull (L)

 

causes L to become an empty list and returns position END(L)

 

8. First (L)

returns the first position on L

 

9.Printlist (L)

print the elements of L in order of occurrence

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.