Comp Sci Intro to Data Structure help (java)

[RedskinsFan]

Hello i am taking a comp sci inro course and i was wondering if anyone here could help me?

 

Here are the questions i am currently trying to answer.

 

1. Complete the following method that determines if two chains of nodes are equal, that is, they have the same strings in the same order. Note two empty chains are considered equal.

       public static boolean equals(Listnode<String> chain1, Listnode<String> chain2) {    

2. Assume the LinkedList class uses a header node with null data. Complete the method below to be added to theLinkedListIterator class. This method inserts item after the node currently pointed to by the iterator. (You may assume that the LinkedList class determines its size by using a loop to count the number of nodes in the chain rather than usingnumItems.) If the item is null the method throws a NoSuchElementException.

       public class LinkedListIterator<E> implements Iterator<E> {	private Listnode<E> curr;         public void insertAfter(E item) {    

3. Assume you want to maintain a LinkedList containing Integers sorted in increasing order. Complete the methodaddInOrder(Integer i) that adds an Integer to a list that is kept sorted. Implement this method to insert the Integer using a LinkedListIterator and insertAfter(...), which you should assume works as described in the previous question. If you need to insert at the beginning of the list, you may use list.add(0, item).

       public class SortedIntegerList {	private LinkedList<Integer> list;         public void addInOrder(Integer i) {    

 

 

Question 1 is giving me problems because i do not understand how i am supposed to compare the two chains of nodes without being able to use a reference for each of the strings in each chain, like you can when comparing arrays.

 

Any help would be greatly appreciated

Thank you

i reposted this in another different forum, the homework help forum. I Didn't notice it until after i posted this

[timo]

Is there a way to iterate over the elements of a Listnode?

[AtomicMaster]

Question 1 is simple, as you iterate over LL1 (or determine its null), also iterate over LL2 and compare the the values. This can be done fairly simply iteratively, or even better recursively.

 

The question i feel like you were asking is more like "how do you iterate over a linked list?", for which you just need to remember how linked lists work. LL maintains the current location pointer, and every node has at least either a previous or next list node pointer, or both a previous and next node pointer (which classifies what kind of an LL it is). The other thing you have to determine is if the list is circular (i.e. does it maintain its starting position, and point the last node's next pointer to the beginning of the list), or flat, in which case last next or last previous pointer will be null.

 

-> LN -> LN -> LN -> - singly linked circular

LN -> LN -> LN -> null - singly linked

null <- LN <- LN <- LN - singly lined (essentially the same as above)

null <-> LN <-> LN <-> null - doubly linked

<-> LN <-> LN <-> - doubly linked circular

 

There are no indexes in the lists, queues, trees, or most other similar structures, like there are in the array; they are totally different data-structures and have different purposes, strengths and weaknesses...