Geek Answers Handbook

Array based sorted linked list

I need to write a java-related list which should be array-based and sorted. Thus, the array contains nodes that have 2 fields: data and the index of the next element in the list. The last item in the list must have an index of -1.

Can someone help how to add an item to such a list. this is the code that I have written so far, but does not seem to be correct, because I can add elements, but the indexes are not right.

package listpackage; import java.io.IOException; public class ArrayLL { private int MAX_CAP = 100; private ANode[] list; private int size; 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); }else{ list[index].setLink(-1); list[0].setLink(index); } }else{ int i = 0; while(list[i].getData() != null){ if(list[index].getData().compareTo(list[i].getData()) < 0){ list[index].setLink(i); if(i>0) list[i-1].setLink(index); }else{ i++; } } } } size++; } public ANode[] getList(){ return list; } public int getSize(){ return size; } } 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 int getLink(){ return link; } public void setLink(int l){ link = l; } }
+4
source share
2 answers

It was great to solve this complex program ... :-) ... I liked it ... here is a working solution ... I tested various scenarios ...

To make sure that I do not change most of your code ... I have not optimized the code. There are many places where the code can be simpler and more readable ...

 import java.io.IOException; public class ArrayLL { public static void main(String[] args) throws IOException { ArrayLL myList = new ArrayLL(); myList.addElem("c"); myList.addElem("b"); myList.addElem("a"); myList.addElem("d"); int i = myList.startOfListIndex; while(myList.list[i].getLink()!=-1) { System.out.println(myList.list[i].getData()); i = myList.list[i].getLink(); } System.out.println(myList.list[i].getData()); } private int MAX_CAP = 100; private ANode[] list; private int size; private int startOfListIndex = 0; public ArrayLL() { list = new ANode[MAX_CAP]; for (int i = 0; i < list.length; i++) { list[i] = new ANode(null); } 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 ANode[] getList() { return list; } public int getSize() { return size; } } 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 int getLink() { return link; } public void setLink(int l) { link = l; } }
+1
source

This is a complete solution, which I believe, since it works for the whole test that I did, but maybe something that I didn’t think about. The solution also includes the removeElem () method.

 package listpackage; import java.io.IOException; 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++; } } } } public ANode[] getList() { return list; } public int getSize() { return size; } } 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; } }
0
source

More articles:


All Articles