Array-based implementation of a sorted linked list

Question

I need to write a java linked list which needs to be array based and sorted. So the array contains nodes which have 2 fields: the data, and the index of the next element in the list. The last element of the list needs to have an index of -1.

Can someone help how to add an element to such list. this is the code I wrote so far but does not seems to be right 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;
    }
}

Aligned with what @gd1 was saying, a LinkedList is a list that does not rely on an Array. An ArrayList would be closer to what you are looking to build here. Or is this some sort of exercise to mix the 2? — blo0p3r
– blo0p3r, Commented Feb 17, 2013 at 22:22
Yes, it's clearly an exercise - but a solid one, in my opinion. @Leon: you didn't say where exactly this element is to be added (to the head of the list, to the tail of the list, or before/after any given element), but the base is more-o-less the same - first create a new element and place it into your container, then modify the links of surrounding elements. — raina77ow
– raina77ow, Commented Feb 17, 2013 at 22:29
So basically the array is used just for "storage" and not for keeping elements sorted? OK, I got it. — gd1
– gd1, Commented Feb 17, 2013 at 22:46
Yes yes the array is just storing nodes. The nodes actually store the array index on the link field for the next element of the list. — Leon
– Leon, Commented Feb 18, 2013 at 1:24

Amit · Accepted Answer · 2013-02-17 23:05:43Z

It was fun to solve this tricky program... :-)... i enjoyed it...here is the working solution...I tested using various scenarios...

In order to make sure I do not change much of your code...I did not optimize the code..there are many places where code can be more simpler and 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;
    }
}

Leon · Accepted Answer · 2013-02-18 02:56:34Z

This is the full solution i believe as it works for all the test i have done, but there might be something i haven't thought of. The solution includes the removeElem() method too.

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;
}
}

Collectives™ on Stack Overflow

Array-based implementation of a sorted linked list

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related