8 Replies - 414 Views - Last Post: 12 February 2019 - 03:52 AM Rate Topic: -----

#1 forumer444   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 44
  • Joined: 19-September 17

stack implementation using linked lists

Posted 07 February 2019 - 02:03 PM

Hi guys, I need help with a homework assignment. I'm just very unclear about what exactly I'm supposed to do. I know I need to implement a stack using a linked list approach, but since I'm new to this, I don't know exactly what the description is telling me I need.

So far, I've created a class called StringBag that implements StringBagInterface (which is listed below) and inherited all of the abstract methods. It says to create a private linked list to hold the inserted strings, so I made a private field LinkedList<String> list;

What I really don't understand is the relationship between a node and the private linked list field. I know what a node is, but am confused on why we need the linked list private field, because every example I see of a stack implementation using a linked list doesn't use a LinkedList object, so I'm confused why I need one here.

My main concern is the insert and remove methods dealing with nodes and the list. Once I understand what to do, I'll be fine filling in the rest of the abstract methods.

Below I'll put the description and the files that I've made so far.

Any advice is appreciated, seriously.

[DESCRIPTION]:
A StringBag Abstract Data Type (ADT) is a simple collection of strings ordered by time of entry (not alphabetical). Like a stack, the last string entered goes “on the top”. The strings are not alphabetized in the bag. Client programs can insert strings into the bag, check its size, clear it, use its toString, remove the “top” string, and check to see if it is full. We want to keep things simple, so we allow duplicates. There is no provision to see if a given string is already in the bag. Further, the client can only remove the string “on top”, like a stack. The StringBag is a LIFO collection. See the StringBagInterface, below. Create a class to implement the interface using a private linked list to hold the inserted strings. Note: if the list is not empty, then the following code will remove the first item in a linked list: head = head.getLink(); Design a test driver that shows that your StringBag.java class works correctly.

interface:
public interface StringBagInterface {

	void insert(String element);
		// Precondition: This StringBag is not full.
		// Places element into this StringBag.

	boolean isFull();
		// Returns true if this StringBag is full, otherwise returns false.

	boolean isEmpty();
		// Returns true if this StringBag contains no strings.

	int size();
		// Returns the number of Strings in this StringBag.

	String remove();
		// Precondition: the Bag is not empty
		// Removes the string “at the top” of the bag and returns it.

	void clear();
		// Makes this StringBag empty. String getName();
		// Returns the name of this StringBag

	String toString();
		// Returns a nicely formatted string representing the
		// name of the bag and all of its contents.

}



StringBag class:
import java.util.LinkedList;

public class StringBag implements StringBagInterface {

	private LinkedList<String> list;
	private Node<String> head;
	private String name;

	public StringBag(String name) {
		this.list = new LinkedList<>();
		this.head = null;
		this.name = name;
	}

	@Override
	public void insert(String element) {
		Node<String> newNode = new Node<>(element);
		newNode.setLink(head);
		head = newNode;
		list.add(element);
	}

	@Override
	public boolean isFull() {
		return false;
	}

	@Override
	public boolean isEmpty() {
		return list == null;
	}

	@Override
	public int size() {
		return list.size();
	}

	@Override
	public String remove() {
		String removedInfo;

		if (isEmpty()) {
			throw new StackUnderflowException("Remove attempted on an empty stack.");
		} else {
			list.removeLast();
			removedInfo = head.getInfo();
			head = head.getLink();
			return removedInfo;
		}
	}

	@Override
	public void clear() {

	}

	@Override
	public String getName() {
		return name;
	}

	@Override
	public String toString() {
		return String.format("list=%s, head=%s, name=%s", list.toString(), head.getInfo(), getName());
	}

}



Node class:
public class Node<T> {

	protected T info;
	protected Node<T> link;

	public Node(T info) {
		this.info = info;
		this.link = null;
	}

	public void setInfo(T info) {
		this.info = info;
	}

	public T getInfo() {
		return info;
	}

	public void setLink(Node<T> link) {
		this.link = link;
	}

	public Node<T> getLink() {
		return link;
	}

}



Is This A Good Question/Topic? 0
  • +

Replies To: stack implementation using linked lists

#2 g00se   User is online

  • D.I.C Lover
  • member icon

Reputation: 3617
  • View blog
  • Posts: 16,595
  • Joined: 20-September 08

Re: stack implementation using linked lists

Posted 07 February 2019 - 03:27 PM

Quote

because every example I see of a stack implementation using a linked list doesn't use a LinkedList object, so I'm confused why I need one here.

Probably there is a list but that list is not an explicit stand-alone class. That, in a way, is an error. You're quite right to use java.util.LinkedList unless you've been told to make your own.

You just need to test your methods and make sure they follow LIFO behaviours
Was This Post Helpful? 0
  • +
  • -

#3 Martyr2   User is offline

  • Programming Theoretician
  • member icon

Reputation: 5359
  • View blog
  • Posts: 14,256
  • Joined: 18-April 07

Re: stack implementation using linked lists

Posted 07 February 2019 - 03:27 PM

Hi forumer444. You are right in the fact that a lot of implementations don't need the internal linkedlist field. I think what your teacher is trying to do is just avoid added complexity by having a LinkedList object handle most of the internal manipulations. You have the internal LinkedList object actually do the storing of the strings. For instance if you were to ask your StringBag to give you the next string (aka call remove()), you would check to see if LinkedList is empty and if not call "pop()" on your linkedlist private field and return that. If you add a string to StringBag (aka call insert()), it would push() the string onto the linkedlist private field.

What this is teaching you as well is that often times classes are "composed" of other data types and objects. A PersonManager might have a private list of people which might be an array, arraylist, stack, whatever. The users of your PersonManager doesn't see how PersonManager works internally. This is a form of encapsulation (aka data hiding). This is type of setup is very very common in programming. All you need to be concerned with is routing what an insert() or remove() on your StringBag class means for interacting with the private LinkedList field.

Also I noticed you said that it asked that you create this LinkedList private field. That was nowhere in your description though. Your description goes under the assumption that you are implementing the linkedlist itself (keeping track of nodes and what other nodes they point to). So perhaps you can clarify for us on that.

This post has been edited by Martyr2: 07 February 2019 - 03:29 PM

Was This Post Helpful? 0
  • +
  • -

#4 forumer444   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 44
  • Joined: 19-September 17

Re: stack implementation using linked lists

Posted 07 February 2019 - 11:03 PM

View PostMartyr2, on 07 February 2019 - 03:27 PM, said:

Also I noticed you said that it asked that you create this LinkedList private field. That was nowhere in your description though. Your description goes under the assumption that you are implementing the linkedlist itself (keeping track of nodes and what other nodes they point to). So perhaps you can clarify for us on that.

In the description, it says "Create a class to implement the interface using a private linked list to hold the inserted strings." Is this not saying to create a private field of the type LinkedList within the StringBag class that implements the interface? Because I think this is my biggest confusion.

This post has been edited by forumer444: 07 February 2019 - 11:03 PM

Was This Post Helpful? 0
  • +
  • -

#5 forumer444   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 44
  • Joined: 19-September 17

Re: stack implementation using linked lists

Posted 07 February 2019 - 11:21 PM

View Postg00se, on 07 February 2019 - 03:27 PM, said:

You just need to test your methods and make sure they follow LIFO behaviours

Are you saying that the insert() and the remove() methods meet the description requirements? Because I'm super confused on why I'd need to use the java.util.LinkedList class when it seems the StringBag class is implementing a linked list itself, by handling the info and link to each element... Like how are the Node objects and links (that i create) connected to the LinkedList<String> field that I add the element to? Wouldn't the private LinkedList field have its own nodes and links associated with that object?

I'm sorry if I'm making things seem complicated. I guess I'm still trying to get my head around this whole idea.

This post has been edited by forumer444: 07 February 2019 - 11:25 PM

Was This Post Helpful? 0
  • +
  • -

#6 g00se   User is online

  • D.I.C Lover
  • member icon

Reputation: 3617
  • View blog
  • Posts: 16,595
  • Joined: 20-September 08

Re: stack implementation using linked lists

Posted 08 February 2019 - 02:29 AM

Quote

Because I'm super confused on why I'd need to use the java.util.LinkedList class when it seems the StringBag class is implementing a linked list itself

Yes, you're right about that. It IS already using it. But you put that in StringBagInterface did you not? Just make sure that the way it's using it means that LIFO is correctly implemented

Your Node class is really redundant, since you already have LinkedList<String>

This post has been edited by g00se: 08 February 2019 - 02:35 AM
Reason for edit:: Clarification

Was This Post Helpful? 0
  • +
  • -

#7 baavgai   User is online

  • Dreaming Coder
  • member icon


Reputation: 7397
  • View blog
  • Posts: 15,330
  • Joined: 16-October 07

Re: stack implementation using linked lists

Posted 08 February 2019 - 02:50 AM

You're confusing yourself, I think.

Of course, your instructions are slightly confusing.

Quote

a simple collection of strings ordered by time of entry (not alphabetical). Like a stack, the last string entered goes “on the top”.

I had to read this over a couple of times. To be clear, this is not "like a stack," it IS a stack.

With what you have, start like this:
// No, you don't need this, don't use this, full stop
// import java.util.LinkedList;

public class StringBag implements StringBagInterface {
    // no private LinkedList<String> list;
    // no private String name;
    private Node<String> head;

    // sign of much confusion.  Why a name here?
    // public StringBag(String name) {
    public StringBag() {
        head = null;
    }



I actually don't like your generic Node class: it's busy and missing a proper constructor. This might be easier if you rolled your own:
public class StringBag implements StringBagInterface {
    private class BagNode {
        public final String value;
        public final BagNode next;
        public BagNode(String value, BagNode next) { /* your code here */}
    }
    private BagNode head;



Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#8 forumer444   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 44
  • Joined: 19-September 17

Re: stack implementation using linked lists

Posted 11 February 2019 - 08:24 PM

Thanks for all the advice, guys, but I honestly can't change things too drastically because my teacher will take points off. So I have to stick that specific Node class.

Here is the final code for the StringBag class. How does it look in terms of what the description says?
I tested it and it seems to implement a stack as far as I can tell.

My only concern is the clear() method. To clear the linked list of LLNode<String> elements, I would just have to set head equal to null, right? That way there's no way to access the elements again and they would be picked up by the garbage collector?

public class StringBag implements StringBagInterface {

	private LLNode<String> head;
	private String name;
	private int size;

	public StringBag() {
		this.head = null;
		this.name = null;
		this.size = 0;
	}

	public StringBag(String name) {
		this.head = null;
		this.name = name;
		this.size = 0;
	}

	@Override
	public void insert(String element) {
		LLNode<String> newNode = new LLNode<>(element);
		newNode.setLink(head);
		head = newNode;
		size++;
	}

	@Override
	public String remove() {
		if (isEmpty())
			throw new StackUnderflowException("remove() was invoked on an empty stack!");

		// store to-be-returned data from top element
		String removedData = head.getData();

		// remove top element
		head = head.getLink();
		size--;

		return removedData;
	}

	@Override
	public void clear() {
		head = null;
		size = 0;
	}

	@Override
	public boolean isFull() {
		return false;
	}

	@Override
	public boolean isEmpty() {
		return head == null;
	}

	public LLNode<String> getHeadElement() {
		return head;
	}

	public void setName(String newName) {
		name = newName;
	}

	@Override
	public String getName() {
		return name;
	}

	@Override
	public int size() {
		return size;
	}

	public void display() {
		LLNode<String> tempNode = head;

		while (tempNode != null) {
			System.out.println(tempNode);
			tempNode = tempNode.getLink();
		}
	}

	@Override
	public String toString() {
		return String.format("head=%s, name=%s, size=%s", getHeadElement(), getName(), size());
	}

}


Was This Post Helpful? 0
  • +
  • -

#9 g00se   User is online

  • D.I.C Lover
  • member icon

Reputation: 3617
  • View blog
  • Posts: 16,595
  • Joined: 20-September 08

Re: stack implementation using linked lists

Posted 12 February 2019 - 03:52 AM

Yes, your thinking is correct
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1