#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    2
    Rep Power
    0

    RemoveAfter - Linked List


    Hi everyone. Nice to meet you. I'm starting studying Linked Lists with Sedgewick's book, Algorithms 4rd edition and I need to do the following assignment from the book:

    Write a method removeAfter() that takes a linked list Node as argument and
    removes the node following the given one (and does nothing if the argument or the next
    field in the argument node is null).
    I think this one is a bit strange because the class Node is private. So, how would I code this method if I can't even create an object of it in the main source? Please help me with a pseudocode for this method. I don't understand linked lists yet.

    Code:
    package stack;
    
    public class LinkedListStack<Item> {
    
        private Node first;
        private int N;
    
        private class Node {
    
            Item item;
            Node next;
        }
    
        public boolean isEmpty() {
            return first == null;
        }
    
        public int size() {
            return N;
        }
    
        public void delete(int k) {
            if (first == null) {
                return;
            }
            Node n = first;
            for (int i = 0; i < k - 1; i++) {
                if (n.next == null) {
                    return;
                }
                n = n.next;
            }
            if (n.next == null) {
                return;
            }
            n.next = n.next.next;
            --N;
        }
        
        public boolean find(Item item) {
    
            Node n;
            for (n = first; n != null; n = n.next) {
                if (n.item == item) {
                    return true;
                }
            }
            return false;
        }
    
        public void push(Item item) {
            Node oldfirst = first;
            first = new Node();
            first.item = item;
            first.next = oldfirst;
            N++;
        }
    
        public void peek() {
            System.out.println("Last node contains: " + first.item);
        }
    
        public Item pop() {
            Item item = first.item;
            first = first.next;
            N--;
            return item;
        }
    }
    Code:
    package stack;
    
    public class LinkedListStackTest {
    
        public static void main(String[] args) {
              
           boolean found = true;
           LinkedListStack<String> lls = new LinkedListStack();  
           
           lls.push("a");
           lls.push("b");
           lls.push("c");
           lls.push("d");
           
           lls.delete(2);
           
           found = lls.find("b");
           if(found)
            System.out.println("The element was found");
           else 
            System.out.println("The element wasn't found");
        }
    }
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,714
    Rep Power
    348
    Does the posted code compile and execute without errors?

    The Node class is only for use by the LinkedListStack class. It is used to chain together Item objects in the linked list.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    2
    Rep Power
    0
    Originally Posted by NormR
    Does the posted code compile and execute without errors.
    yep.
  6. #4
  7. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,714
    Rep Power
    348
    First thing to do is use a pencil and paper and draw a diagram of a linked list.
    Then work out the simple, single steps that need to be done to remove the desired item.
    When you have the list of steps the program needs to do, then look at coding it.

IMN logo majestic logo threadwatch logo seochat tools logo