Write a separate program to simulate (represent) a linked list structure using arrays one Array (name it linkedList) that will contain the data in the linked list

ANSWER ALL QUESTIONS

1. Write a separate program to simulate (represent) a linked list structure using arrays. You will need the following data structures:

   1. One Array (name it linkedList) that will contain the data in the linked list (e.g. integer values).

   2. Another integer array (name it forwardPointer) that will serve as a corresponding set of forward pointers.

   3. A single external field (integer) named front that will point to the front of the linked list (the first element in the list).

   4. A single external field (integer) named rear that will point to the rear of the linked list (the last element in the list).

For example,

linkedList:  4, 6, 8, 23, 66, 91, 36, 75, 84

So, linkedList [0] = 4, linkedList [4] = 66, etc…

front will contain the value 0 (the index of the first element)

rear will contain the value 8 (the index of the last element

forwardPointer: 1, 2, 3, 4, 5, 6, 7, 8, -    (“-“ indicates a pointer beyond the end of linkedList, or null.)

i.e., forwardPointer[2] will initially have the value 3, which points to linkedList[3], or the value 23. You can read this as: “ the element in linkedList indexed by 2 points to the element in linkedList indexed by 3. Note that the value 3 in forwardPointer is then itself used as an index in the array linkeList to point to the next element in the list. ”

Within your program, provide methods that will perform the following functions:

• insertElement(afterElement, newElement) that will insert an element anywhere within the middle of the linked list (not before the front or after the rear).
• removeElement(elementValue) that will remove (delete) an element from the middle of the list (not the front or the rear)

For example, if you wanted to insert the element 12 after 66 in the array linkedList, you would simply add an element of value 12 to the end of the linkedList array, and then manipulate the forwardPointer array accordingly. After the insert operation,  the two arrays should result in the following configuration:

linkedList:           4,  6, 8, 23, 66, 91, 36, 75, 84, 12

forwardPointer: 1, 2, 3,   4,   9,   6,    7,   8,   -   , 5

Note that the array elements themselves are not moved from their original positions in the array. The inserted element (12) is simply added at the end of the array  ( position 9), and then the forwardPointer array is updated accordingly: linkedList [4] (66) is now pointing to element linkedList[9] instead of linkedList[5]. Note also that the newly inserted  element (12) now points to position 5 in the linkedList array.

It is left as an exercise for the student to determine the steps involved in a removeElement(elementValue) operation.

Attachments:

Related Questions

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of