Occasionally, a linked structure that does not use references is useful. One suc
ID: 3908261 • Letter: O
Question
Occasionally, a linked structure that does not use references is useful. One such structure uses an array whose items are "linked" by array indexes. Figure 5-35a illustrates an array of nodes that represents the linked list in Figure 5-31. Each node has two data fields, item and next. The next data field is an integer index to the array element that contains the next node in the linked list. Note that the next data field of the last node contains -1. The integer variable head contains the index of the first node in the list. The array elements that currently are not a part of the linked list make up a free list of available nodes. These nodes form another linked list, with the integer variable free containing the index of the first free node. To insert an item into the original linked list, you take a free node from the beginning of the free list and insert it into the linked list (Figure 5-35b). When you delete an item from the linked list, you insert the node into the beginning of the free list (Figure 5-35c). In this way, you can avoid shifting data items. Implement the ADT list by using this array-based linked list.Explanation / Answer
Since you jave not provided the language of your preference, I am providing the code in Java.
CODE
=================
import java.io.IOException;
import java.util.Arrays;
public class ArrayLL {
private int MAX_CAP = 100;
private ANode[] list;
private int size;
private int startOfListIndex = 0;
public ArrayLL() {
list = new ANode[MAX_CAP];
list[list.length-1] = new ANode(null, -1);
for(int i = 0; i < list.length-1; i++){
list[i] = new ANode(null, i+1);
}
size = 0;
}
public void addElem(String s) throws IOException {
if (this.getSize() == 0) {
ANode a = new ANode(s, -1);
list[0] = a;
}else if (size == MAX_CAP + 1) {
throw new IOException("List is full");
}else{
int index = 0;
for (int i = 0; i < list.length; i++) {
if (list[i].getData() == null) {
index = i;
break;
}
}
ANode b = new ANode(s);
list[index] = b;
if (this.getSize() == 1) {
if (list[index].getData().compareTo(list[0].getData()) < 0) {
list[index].setLink(0);
list[0].setLink(-1);
startOfListIndex = index;
} else {
list[index].setLink(-1);
list[0].setLink(index);
}
} else {
int i = startOfListIndex;
int prevIndex = -1;
while (i!=-1 && list[i].getData() != null) {
if (list[index].getData().compareTo(list[i].getData()) < 0) {
list[index].setLink(i);
if(prevIndex!=-1)
list[prevIndex].setLink(index);
else
startOfListIndex = index;
break;
}else{
prevIndex = i;
i=list[i].getLink();
}
}
if(i==-1)
{
list[prevIndex].setLink(index);
}
}
}
size++;
}
public void removeElem(String s) throws IOException {
if (this.getSize() == 0) {
throw new IOException("List is empty");
}else{
int firstEmpty = 0;
for(int i = 0; i< list.length; i++){
if(list[i].getData() == null){
firstEmpty = i;
break;
}
}
int elemindex = 0;
int prev = -1;
int next=-1;
for(int i = 0; i < list.length; i++){
if(list[i].getData() != null && list[i].getData().compareTo(s) == 0){
elemindex = i;
next = list[i].getLink();
for(int j = 0; j < list.length; j++){
if(list[j].getLink() == elemindex){
prev = j;
break;
}
}
list[elemindex].setDataNull();
list[elemindex].setLink(firstEmpty);
if(next != -1)
list[prev].setLink(next);
else
list[prev].setLink(-1);
size--;
}else{
elemindex++;
}
}
}
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "ArrayLL [MAX_CAP=" + MAX_CAP + ", list=" + Arrays.toString(list) + ", size=" + size
+ ", startOfListIndex=" + startOfListIndex + "]";
}
public void display() {
int i=0;
while(list[i].getData() != null) {
System.out.print(list[i] + " ");
i ++;
}
}
public ANode[] getList() {
return list;
}
public int getSize() {
return size;
}
public static void main(String args[]) {
ArrayLL list = new ArrayLL();
try {
list.addElem("B");
list.addElem("E");
list.addElem("J");
list.addElem("D");
System.out.println("Now, the list is: " + list.getList());
list.removeElem("B");
System.out.println("After removing D, the list is : ");
list.display();
} catch(Exception e) {
e.printStackTrace();
}
}
}
class ANode {
private String data;
private int link;
public ANode(String d) {
data = d;
link = -1;
}
public ANode(String d, int l) {
data = d;
link = l;
}
public String getData() {
return data;
}
public void setDataNull(){
this.data = null;
}
public int getLink() {
return link;
}
public void setLink(int l) {
link = l;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "ANode [data=" + data + ", link=" + link + "]";
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.