Results 1 to 6 of 6
  1. #1
    jumper007 is offline Member
    Join Date
    Mar 2014
    Posts
    4
    Rep Power
    0

    Question LinkedList Issue

    Hello everybody, first of all, I want to say that I'm new here so greetings to you all :)
    Secondly, on-topic, I know that Java offers a build in LinkedList data structure, but I am writing my own for educational purposes (learning data structures), and this is just a way of practice (otherwise I would use the build in function).

    Now, I have been implementing this LinkedList, but came across a weird bug, whose cause I cannot really figure out. I would really appreciate it if you could help me with this. So, long story short, here is my code (I have 3x .java files):

    Node.java - in "helper" package
    Java Code:
    package helper;
    
    public class Node<T> {
    	public T value;
    	public Node<T> next;
    	public boolean flag;
    	
    	// Constructors
    	public Node(T newValue) {
    		value = newValue;
    		next = null;
    		flag = false;
    	}
    	
    	public Node() {
    		next = null;
    		flag = true;
    	}
    	
    	// Print node
    	public void printNode() {
    		System.out.print("{" + value + "} ");
    	}
    }
    LinkedList.java - in "source" package
    Java Code:
    package source;
    
    import helper.Node;
    
    public class LinkedList<T> {
    	private Node<T> front, back;
    	
    	// Constructor
    	public LinkedList() {
    		front = null;
    		back = front;
    	}
    	
    	// Check if empty
    	public boolean isEmpty() {
    		return (front == null);
    	}
    	
    	// Get first node
    	public Node<T> front() {
    		return front;
    	}
    	
    	// Get last node
    	public Node<T> back() {
    		return back;
    	}
    	
    	// Find node in list (any position)
    	public Node<T> find(T value) {
    		Node<T> current = front;
    		while (current.value != value && current.next != null) {
    			current = current.next;
    		}
    		if (current != back) {
    			return current;
    		}
    		return (new Node<T>());
    	}
    	
    	// Insert node in list (any position)
    	public void insert(Node<T> nodeBefore, T value) {
    		Node<T> newNode = new Node<T>(value);
    		Node<T> temp = nodeBefore.next;
    		nodeBefore.next = newNode;
    		newNode.next = temp;
    	}
    	
    	// Push node in front of the list
    	public void push_front(T value) {
    		Node<T> temp = new Node<T>(value);
    		if (front == null) {
    			front = temp;
    			back = temp;
    		}
    		else {
    			temp.next = front;
    			front = temp;
    		}
    	}
    	
    	// Push node at the end of the list
    	public void push_back(T value) {
    		Node<T> temp = new Node<T>(value);
    		if (front == null) {
    			front = temp;
    			back = temp;
    		}
    		else {
    			back.next = temp;
    			back = temp;
    		}
    	}
    	
    	// Delete node (any position)
    	public void erase(Node<T> node) {
    		Node<T> current = front;
    		while (current.next != null) {
    			if (current == node) {
    				if (current.next.next != null) {
    					current.next = current.next.next;
    				}
    				break;
    			}
    			else {
    				current = current.next;
    			}
    		}
    	}
    	
    	// Delete first node
    	public void pop_front() {
    		if (front.next != null) {
    			front = front.next;
    		}
    	}
    	
    	// Delete last node
    	public void pop_back() {
    		Node<T> current = front;
    		while (current.next.next != null) {
    			current = current.next;
    		}
    		current.next = null;
    		back = current;
    	}
    	
    	// Print the list
    	public void printList() {
    		Node<T> current = front;
    		while (current != null) {
    			current.printNode();
    			current = current.next;
    		}
    		System.out.println("");
    	}
    }
    Test.java - in "usage" package
    Java Code:
    package usage;
    
    import helper.Node;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    import source.LinkedList;
    
    public class Test {
    	// Main function - call tests
    	public static void main(String[] args) {
    		testLinkedList();
    	}
    	
    	// TestingLinkedList
    	public static void testLinkedList() {
    		LinkedList<String> list = new LinkedList<String>();
    		
    		InputStreamReader streamReader = new InputStreamReader(System.in);
    		BufferedReader in = new BufferedReader(streamReader);
    		
    		Node<String> searchResult;
    		String var, save1, save2, save3;
    		
    		try {
    			do {
    				var = in.readLine();		
    				list.push_back(var);
    			} while (!var.matches("."));
    		}
    		catch (IOException err) {
    			System.out.println(err);
    		}
    		
    		System.out.println("#1 List:");
    		list.printList();
    		
    		list.push_front("Java");
    		list.push_front("Welcome To");
    		list.push_back("I'm the last line");
    		list.push_back("No! I'm the last line");
    		
    		System.out.println("#2 List:");
    		list.printList();
    		
    		searchResult = list.find("I'm the last line");
    		if (searchResult.flag == false) {
    			list.insert(searchResult, "Sigh");
    			list.erase(searchResult);
    		}
    		
    		list.pop_front();
    		list.pop_back();
    		
    		System.out.println("#3 List:");
    		list.printList();
    		
    		save1 = list.front().value;
    		save2 = list.back().value;
    		
    		searchResult = list.find("Sigh");
    		if (searchResult.flag == false) {
    			save3 = searchResult.value;
    		}
    		else {
    			save3 = null;
    		}
    		
    		System.out.println("#4 Words:");
    		System.out.println("{" + save1 + "} {" + save2 + "} {" + save3 + "}");
    	}
    }
    The problem with the code is that in the Test.java file, when it reaches this block of code:
    Java Code:
    searchResult = list.find("I'm the last line");
    if (searchResult.flag == false) {
    	list.insert(searchResult, "Sigh");
    	list.erase(searchResult);
    }
    It doesn't insert the text "Sigh", and it doesn't erase the text "I'm the last line" as it should. The rest works perfect. I've no idea where the problem might be, but if you spot the issue, please let me know :)

    Thanks in advance! :D

    Yours sincerely,
    Raul.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: LinkedList Issue

    Try debugging the code by adding some println() statements that print out the value of variables as they are changed so you can see what the computer sees when it executes the code.
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    jumper007 is offline Member
    Join Date
    Mar 2014
    Posts
    4
    Rep Power
    0

    Default Re: LinkedList Issue

    Thanks, I'll try doing that, but it'll be tomorrow in like 16 hours from now (got to go now -- it's really late here -- and tomorrow I'll be quite busy) :)

  4. #4
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,411
    Rep Power
    5

    Default Re: LinkedList Issue

    Have you researched linked lists at all? It looks like you are implementing a linked list which acts like a stack. So what capabilities do you want in the linked list?

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  5. #5
    jumper007 is offline Member
    Join Date
    Mar 2014
    Posts
    4
    Rep Power
    0

    Default Re: LinkedList Issue

    Well, to be honest, I tried to create something like the list type in C++ (Standard Template Library): list - C++ Reference
    I'm usually programming in C/C++ and switched to Java recently, so I just took that one as a reference, tho if it's wrong, please correct me, I'm willing to learn it the right way :)

    EDIT: Actually, I should've specified that this would be a doubly linked list eventually (having access to both the beginning and the end of the list, and being able to perform operations on both of those).

    Yours,
    Raul
    Last edited by jumper007; 03-17-2014 at 11:01 PM.

  6. #6
    jumper007 is offline Member
    Join Date
    Mar 2014
    Posts
    4
    Rep Power
    0

    Default Re: LinkedList Issue

    Okay, so, I just got some free time now, and took a look over my code again. I knew the problem was somewhere at the insert and erase methods, but I finally understood what the problem was.. In the erase method I was erasing the newly added element (ie: the element AFTER the one that I wanted to delete). Tho, thanks for the help guys. In case anyone wonders, here's the correct erase method:

    Java Code:
    // Delete node (any position)
    	public void erase(Node<T> node) {
    		Node<T> current = front;
    		while (current.next != back) {
    			if (current.next == node) {
    				if (current.next.next != null) {
    					current.next = current.next.next;
    				}
    				break;
    			}
    			else {
    				current = current.next;
    			}
    		}
    		if (current.next == back && current.next == node) {
    			current.next = null;
    			back = current;
    		}
    	}
    Yours,
    Raul

Similar Threads

  1. What does LinkedList.Node head = linkedList.head(); does?
    By Jack_Tauson_Sr in forum New To Java
    Replies: 1
    Last Post: 04-19-2013, 08:32 AM
  2. Regular Expression issue and setName() method issue
    By geforce in forum New To Java
    Replies: 2
    Last Post: 01-30-2012, 03:33 AM
  3. I need help in LinkedList ...
    By Usman in forum Advanced Java
    Replies: 3
    Last Post: 03-25-2011, 01:38 AM
  4. LinkedList help
    By jigglywiggly in forum New To Java
    Replies: 6
    Last Post: 09-19-2009, 07:24 AM
  5. Java LinkedList Issue
    By Arunkumar in forum Advanced Java
    Replies: 6
    Last Post: 09-18-2009, 07:26 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •