Convert Linkedlist to ArrayList
I had to write a program to do LZWDecode and I decided to use LinkedList to write the LZWDecode program below but I want to convert it to an ArrayList. Anyone have idea on how I can convert the LinkedList to an ArrayList to make it simpler. Thanks.
import java.util.*; public class LZWDecoder < private final int CLEAR_TABLE=256; private final int END_OF_DATA=257; private final int TABLE_SIZE=4096; private static LinkedListinput = new LinkedList(); @SuppressWarnings("unchecked") private LinkedList[] table = new LinkedList[TABLE_SIZE]; private LinkedList temp = new LinkedList(); private int index = 258; private LinkedList trace = new LinkedList(); private boolean view = true; private void enterData() < Scanner scan = new Scanner(System.in); System.out.println("Please enter the Input Code (EOD = 257):"); int n=0; while(n!=END_OF_DATA && scan.hasNextInt())< n = scan.nextInt(); //System.out.println("Adding "+n); input.add(n); >System.out.println("Decoding. \nOutput:"); String code=""; for(int i=0; i trace.add("\nInput: "+code); //test /* while(!input.isEmpty()) < System.out.println(input.remove()); >*/ > private void reset() < trace.add("Clearing. "); //table.clear(); for(int i=0; i > private void decode(int c) < switch(c) < case CLEAR_TABLE: trace.add("decode\t"+CLEAR_TABLE+"->[256]"); reset(); break; case END_OF_DATA: trace.add("decode\t"+END_OF_DATA+"->[257]"); trace.add("Decoding finished."); break; default: if(c<256) < trace.add("decode\t"+c+"->["+c+"]"); if(!temp.isEmpty()) append(c); emit(c); add(temp); > else < trace.add("decode\t"+c+"->["+printTableNode(table[c])+"]"); if(!temp.isEmpty()) append(table[c].get(0)); emit(c, table[c]); add(temp); > > > private void emit(int n, LinkedList c) < //int [] a=new int[c.size()]; temp=new LinkedList(); for(int i=0; i trace.add("emit\t"+n+"->"+"["+printTableNode(c)+"]"); > private void emit(int c) < //print out output temp=new LinkedList(); temp.add(c); trace.add("emit\t"+c+"->"+"["+c+"]"); System.out.print(c+" "); > /* private void add(int c) < //added to table is copied to temp table[index].add(c); temp = (LinkedList)table[index].clone(); trace.add("add\t"+index+"->["+printTableNode(table[index])+"]"); > */ private void add(LinkedList c) < for(int i=0; itrace.add("add\t"+index+"->["+printTableNode(table[index])+"]"); > private void append(int c) < //table[c].add(12);//add what? //temp.add(c); table[index].add(c); trace.add("append\t"+index+"->["+printTableNode(table[index])+"]"); index++; > private String printTableNode(LinkedList l) < String list=""; for(int i=0; i> return list; > private void printTrace() < System.out.print("Printing Trace. "); for(int i=0; i> public static void main(String[] args) < // TODO code application logic here LZWDecoder d = new LZWDecoder(); d.enterData(); while(!input.isEmpty()) < d.decode(input.remove()); >System.out.print("\n\n"); d.printTrace(); > > Array of Linked Lists Java
I am trying to create an array of linked lists The program I am trying to write has a string array of names, however some names are in the same position of the array. For example if the name morgan is in array[0] and john is also in array[0] how can I create a linked list that allows both of the names to be stored in the same index. I am trying to replicate separate chaining collision resolution. Is it possible to use LinkedList
From what I understand. You don’t need to do much. Just keep adding the names to the list accessing the same array location. Suppose you have a name in arr[0]. Create a new node for the list at arr[0] and just add another name to that list accordingly.
2 Answers 2
I don’t know if I understand your question. Here is your question. you are trying to create an array of linked lists The program has ‘a string array’ of names,
: You have String name in the node if you add correctly, you will get the linkedlist.
however some names are in the ‘same position’ of the array. For example if the name morgan is in array[0] and john is also in array[0] how can I create a linked list that allows both of the names to be stored in the same index.
: How about adding one more Sting in the object, it that what you want?
Not sure if I started correctly but this is what I have so far
: You should start with a constructor first and make add, delete, and other functions.
public Class CustomList < private CustomList head; private int index = 0; private Class Node< private String firstName; private String secondName; private Node next; **constructor** public Node(String firstName, String secondName)< this.firstName = firstName; this.secondName = secondName; next = null; >> **constructor** public CustomList() < head = null; >> The above will contain two String values in the same index of CustomList. If I understood the question wrong or you have any more question feel free to ask.
How to add to an arraylist of linkedlists?
I am sorry if this is a stupid question but I am new to Java linkedlists and arraylists. What I wish to do is this: I have a text file that I run through word for word. I want to create an Arraylist of linkedlists, which each uniqye word in the text followed in the linked list by the words that it is followed by in the text. Consider this piece of text: The cat walks to the red tree. I want the Arraylist of LinkedLists to be like this: The — cat — red | cat — walks | to — the | red — tree What I have now is this:
while(dataFile.hasNext()) < secondWord = dataFile.next(); nWords++; if(nWords % 1000 ==0) System.out.println(nWords+" words"); //and put words into list if not already there //check if this word is already in the list if(follows.contains(firstWord))< //add the next word to it's linked list ((LinkedList)(firstWord)).add(secondWord); >else< //create new linked list for this word and then add next word follows.add(new LinkedList().add(firstWord)); ((LinkedList)(firstWord)).add(secondWord); > //go on to next word firstWord = secondWord; > And it gives me plenty of errors. How can I do to this the best way? (With linkedlists, I know hashtables and binary trees are better but I need to use linked lists)
Forget about using LinkedList or ArrayList , and thus forget about this type cast as well. Declare your variables as List interface, and when initializing it decide the proper class implementation.
2 Answers 2
An ArrayList is not the best data structure for purpose of your outer list, and at least part of your difficulty stems from incorrect use of a list of lists.
In your implementation, presumably follows is an ArrayList of LinkedLists declared like this:
ArrayList> follows = new ArrayList<>(); The result of follows.contains(firstWord) will never be true, because follows contains elements of type LinkedList, not String. firstWord is a String, and so would not be an element of follows , but would be the first element of an ArrayList which is an element of follows .
The solution offered below uses a Map , or more specifically a HashMap , for the outer list follows . A Map is preferable because when searching for the first word, the amortized look-up time will be O(1) using a map versus O(n) for a list.
String firstWord = dataFile.next().toLowerCase(); Map> follows = new HashMap<>(); int nWords = 0; while (dataFile.hasNext()) < String secondWord = dataFile.next().toLowerCase(); nWords++; if (nWords % 1000 == 0) < System.out.println(nWords + " words"); >//and put words into list if not already there //check if this word is already in the list if (follows.containsKey(firstWord)) < //add the next word to it's linked list List list = follows.get(firstWord); if (!list.contains(secondWord)) < list.add(secondWord); >> else < //create new linked list for this word and then add next word List list = new LinkedList(); list.add(secondWord); follows.put(firstWord, list); > //go on to next word firstWord = secondWord; > The map will look like this:
the: [cat, red] cat: [walks] to: [the] red: [tree] walks: [to] I also made the following changes to your implementation:
- Don’t add duplicates to the list of following words. Note that a Set would be a more appropriate data structure for this task, but you clearly state that a requirement is to use LinkedList .
- Use String.toLowerCase() to move all strings to lower case, so that «the» and «The» are treated equivalently. (Be sure you apply this to the initial value of firstWord as well, which doesn’t appear in the code you provided.)
Note that both this solution and your original attempt assume that punctuation has already been removed.
Can you create an array of linked lists in Java?
Is it possible to create an array of linked lists? Or an arraylist of linked lists? I’ve been searching everywhere and seem to be getting contradicting answers. I’ve seen «no» answers that state that it can’t be done because you can’t make an array of things that can be dereferenced. I’ve seen «yes» answers that state it can be done and they end there. Thanks in advance.
@LuiggiMendoza — it shold be fairly obvious that ?? needs to be replaced by an actual type parameter.
@Perception compiler will complain saying generic array creation, next time compile the code before proposing it as solution.
3 Answers 3
If I understand you right, you basicly want to make a 2D Array, but with the second half being a linked list.
import java.util.ArrayList; import java.util.LinkedList; public class Test < public static void main(String[] args) < LinkedList one = new LinkedList(); LinkedList two = new LinkedList(); LinkedList three = new LinkedList(); ArrayListarray = new ArrayList(); array.add(one); array.add(two); array.add(three); // .. do stuff > > Java doesn’t care what the Objects in Arrays or Lists are, so there’s nothing against putting another Array or List in.
If set up this way, does each LinkedList get a pointer that has a different name? Or can pointers have the same name for different LinkedLists? (For example, if I want to transverse a linked list, I need to move a pointer along — current = current.next. Could each individual linked list have the same name for the pointers? Or do I need to have different pointer names for each list, eg, currentOne, currentTwo, currentThree, etc.)
I would recommend you should use multiple pointers, if for no other reason than to keep your code cleaner and easier to understand, but you could probably get away with using (current.next).next (or something similar).