Assistance with creating java Linked Lists using only nodes

You are getting close. First of all a linked list is a list of objects, commonly called nodes, each of which has one or more links to other objects. In your case the nodes are Aircraft.

This should help you a bit: Wikipedia:Linked List

Your main problem so far is that you do not have links in your Aircraft class. Since this is a linked list you need to include the reference to the next element in the list. Within the Aircraft class you should have a property called next of type Aircraft that links you to the next Aircraft in your list. This allows you to call myAircraft.next, as you are in your code so far, which will allow you to travel down the list in order. I'll leave you to figure out the rest yourself, this is homework, but feel free to comment if you need any more explanation.

I think you are pretty close - but it's hard to tell exactly what's going on in your ATControl class. Typically the add method on a linked list takes a node (in your case an Aircraft), not a number.

The key to a linked list is that each node has a pointer to the next one in the list. In your Aircraft class, you have: Aircraft next, which will serve as that pointer.

I would suggest implementing the following methods in ATControl:

public static Aircraft getUserInput(Scanner in)
{
  Aircraft aircraft = new Aircraft();

  // get your values from the user and set them in your new aircraft
  return aircraft;
}

public static void add(Aircraft aircraft) 
{
  // starting at head, walk through the list (repeatedly call next on 
  // the current Aircraft) until you reach the desired position 

  Aircraft temp = head;

  while (temp != null) // ...
}

public static void remove(String flightNum)
{
  // again, the same way you did in add, walk through the list until you find it
    if (current.getName().equals(flightNum))
      // we found it, so remove it
}

Unless you have a very firm grasp on OOP and reference types, attempting to write a LinkedList implementation is a practice in masochism.

The following is going to be long and possibly painful/humiliating. That's OK, it'll be a good learning experience. I'm putting a lot of effort into this to provide a complete implementation with thorough commenting. I suggest you read the details closely until you fully understand their purpose.

First, fix your Aircraft class. Since you'll need to create multiple instances, static members won't work. If you don't understand why, take some time to brush up on your OOP fundamentals.

List nodes should be designed to store minimal data. In your case it looks like you're most of the way there. There is flight data specific to each node and a reference to the next item in the list. That's all you need.

Without all the extra cruft here's what it looks like:

public class Aircraft  {
    public String name;
    public String type;
    public int speed;
    public int alt;
    Aircraft next;

    public Aircraft (String n, String t, int s, int a) {
        name = n;
        type = t;
        speed = s;
        alt = a;
        next = null;
    }
}

Looking good. It's safe to assume that this has all of the necessary functionality built-in.

Feel free to add the following back in if you want:

• setName()
• getName()
• setType()
• getType()
• setSpeed()
• getSpeed()
• setAlt()
• getAlt()

Note: These will only work if they're not set to static. Unless you plan to pass the Aircraft instance being changed in as one of the arguments every time you call it. Trust me, using instance methods is a lot easier.

Changes:

• I removed the Aircraft() constructor. At a minimum, you'll need to initialize an Aircraft node with at least a flight number (or some other unique identifier) or you won't be able to find the Aircraft in the list later.

• removeName() is useless. Since the individual nodes are only aware of the next item in the list they are incapable of removing themselves. If you used a doubly-linked-list where each node stores references to both the previous and next nodes then it would be possible but there really is no need. Same goes for the add() and remove()* methods. Additions/removals are handled in the **ATControl class.

• There's not much need for getNext() or setNext() either. Since ATControl is used to maintain state of the list (ex size, capacity, etc) you won't want to make nextCraft publicly accessible via getters/setters.

Now for ATControl:

public class ATControl {
    private Aircraft head; // stores the start of the chain
    private Aircraft tail; // stores the end of the chain
    private int size; // stores the length of the chain

    public ATControl() {
        // ♫ "Started from the bottom now we're herre' ♫
        // Seriously, the list should start with nothing
        head = null;
        tail = null;
        size = 0;
    }

    public void addFlight(String flight, String plane, int speed, int alt) {
        // TODO: Implement this
    }

    public void removeFlight(String name) {
        // TODO: Implement this 
    }

    public void displayFlight(String name) {
        // TODO: Use a foreach loop to find and display a flight
    }

    public void displayAll() {
        // TODO: Use a foreach loop to display the flights here
    }
}

Changes:

• I removed the main* member because I don't have the slightest idea how it works here. Either way, to use this you'll need to create a new **ATControl instance.

• I removed the inline variable declarations because that's instance members have to be set in the constructor.

• The head and tail are initialized to null because no Aircraft have been added yet.

• I removed the aircraft member because it will never be used.

• Unless you only expect to create one ATControl instance, you shouldn't set head and tail too static either. If either of them are changed by anything but ATControl, it'll screw up the internal state of the list so they should be set to private.

• I removed the size constraint because it's not necessary to make this work. You can add it back in later if you want.

• I axed Nodes() and addNodes() for two reasons. First, it both violate the SRP (Single Responsibility Principle) because they are responsible for creating a node and a collection of nodes. Second -- I'm assuming it's a bug but -- you were passing in the flight number as the number of nodes you wanted to create. Ex, if the flight number were 1457 you'd be adding 1457 empty nodes to the list.

• I renamed addToList() to addFlight() to keep things consistent. I also renamed showFlight() to displayFlight() for consistency. For the sake of simplicity and to make this class useful to more than just command-line inputs I also removed the user input parts.

I know, I know! I'm a merciless butcher but now the code is in a good position to start building in the necessary functionality.

First things first. If you don't know to make a class iterable (ie work as a foreach loop) you're about to find out. I'll need to add some more stuff to ATControl but it'll be fun.

public class ATControl implements Iterable {
    private Aircraft head;
    private Aircraft tail;
    private int size;

    public ATControl() {
        head = null;
        tail = null;
        size = 0;
    }

    public void addFlight(String flight, String plane, int speed, int alt) {
        // if the list is not currently empty
        if (!isEmpty()) {
            // store a reference to the last Aircraft in the list
            Aircraft prev = tail;
            // create a new aircraft and add it to the end of the list  
            tail = new Aircraft(flight, plane, speed, alt);
            // link the old tail to the new tail
            prev.next = tail;
        }
        // an empty list needs to be handled a little differently
        else {
            // notice, with no tail there's no tail to update
            tail = new Aircraft(flight, plane, speed, alt);
            // also, since there's only one item the head and tail are the same
            head = tail;
        }
        size++;
    }

    // The hard part. Lots of nasty edge cases.
    // Creating one of these from scratch will make your head hurt.
    // Note: Setting variables to null marks them for the garbage collector.
    // SideNote: With a doubly-linked list you can do removals within a foreach loop
    public void removeFlight(String flight) {
        Node prev = head;
        Node curr = head;
        // crawl the list looking for a match
        while (curr.next != null || curr == tail) {
            if (curr.flight.equals(flight)) {
                // if there is only one item left, null everything
                if (size == 1) { head = null; tail = null; }
                // reset the head to start at the second Aircraft
                else if (curr.equals(head)) { head = head.next; }
                // reset the tail to end at the 2nd-to-last Aircraft
                else if (curr.equals(tail)) { tail = prev; tail.next = null; }
                // if it's in the middle, re-connect the broken links on either end
                else { prev.next = curr.next; }
                size--;
                break;
            }
            prev = curr;
            curr = prev.next;
        }
    }

    public boolean isEmpty() {
        return size == 0; // only returns true if size is 0

    // The fun part. The following are necessary to make the list iterable
    // Like magic, this class will now be callable as a foreach loop
    public Iterator<Aircraft> iterator() { return new ATCIterator(); }

    // This iterator code can be reused on any linked-list implementation
    // Keep this handy in case you need to implement Iterable in the future
    private class ATCIterator implements Iterator<Aircraft> {
        private Aircraft current = head;

        public Aircraft next() {
            if (!hasNext()) { throw new NoSuchElementException(); }
            Aircraft aircraft = current;
            current = current.next;
            return aircraft;
        }

        public boolean hasNext() { return current != null; }

        // inline removals require a doubly linked list. To reconnect the break 
        // in the chain the node has to be aware of both the previous and next nodes.
        public void remove() { throw new UnsupportedOperationException(); }
    }

    // lets put that foreach loop functionality to good use now.

    // Bonus: use this to retrieve the matching Aircraft instance
    // Once you have a reference to the Aircraft instance you can do things like
    // get/set it's internal values.
    public aircraft getFlight(String flight) {
        for (Aircraft aircraft : this)
            if (this.flight == flight) {
                return this;
    }


    // displays the flight number of the first match
    public void displayFlight(String flight) {
        for (Aircraft aircraft : this)
            if (this.flight == flight) {
                System.out.printf("Flight: " + flight);
                // Note: you can access the Aircraft details here via the 'this' keyword
                return;
    }

    // crawls the whole list and displays the flight number of every aircraft
    public void displayAll() {
        for (Aircraft aircraft : this)
            System.out.printf("Flight: " + flight);
            // Note: you can access the flight details here via the 'this' keyword
    }
}

So, you have a wall of code with lots of comments to chomp on. Time for some theory.

What makes a LinkedList a LinkedList anyway?

It's literally just a bunch of object instances that are randomly placed on the heap and linked together via references (or pointers for the C crowd).

Imagine a LinkedList as a Samba Line.

Source: The Traveling Eye Blog

Note: A doubly-linked list is the same except the line can change directions.

Every person is holding on to the person in front of them but they can't see who is behind them. Adding to a list is like adding a person to the front of the line. Technically, the LinkedList I wrote works in the opposite direction with additions being added to the front and removals being cut from the tail but the concept is the same.

Fetching/removing an item from the list is like adding a limbo pole. The first hit gets taken out of the chain and the break is mended by reconnecting the ends of the break.

The benefit to using a LinkedList is that it can be as big or as small as you want. You're free to add/remove nodes however you want.

The downside is, unlike an array there's no way to fetch an item from within the list without first walking the chain of links. Also, the overhead of all those class instances and references starts to get expensive when the list grows very large.

In performance terms it takes O(1) (ie constant time) to add items. O(N) (ie linear time) to fetch/remove items from the list. And, depending on whether the list is single/double and/or jump linked there is a notable memory overhead involved.

There are other data structures like ArrayLists, HashMaps, etc that have better performance or memory characteristics for use cases like yours but they're even more complicated to write/manage.

The easiest way to get all the magical goodness of a high-level data structures without the work is to wrap and extend an existing implementation. For example, you could create a class that uses an ArrayList internally for data storage. You can even make it iterable using the methods I demonstrated above. Except, instead of being written for any generic type it can be customized to work use your Aircraft data type.

Note: If you want to learn how to write data structures I suggest you take an Algorithms I class online (or otherwise).

Here is a link to what the re ponders are referring to when they say a list. Here is a link http://www.algolist.net/Data_structures/Singly-linked_list/Traversal that explains list. However, I'm not sure this is representative in java. The code you wrote looks like you are not sorting but adding all airplanes at the end of the list. Therefore the list is not sorted. When you make temp.next = tail is making the last airplane in the list point to itself rather than null. But you aren't checking for null you are counting the number of planes in the list. I posted a java example, where you have a node class with a node next, you should add node tail as well since your code is using it.

public class Node {

   public int item;
   public Node next;
   public Node tail;


   Node() {                 
      item = 0; 
      next = null; 
       tail = null ;    
   } 

   Add Node(node tail, node new) {

      tail.next = new;
        tail.tail = new
        new.tail =null

   }

};

I hope I didn't make it worse. Good luck.

airplane class can extend the node class. Look at the childfactory class in java. It will give you an example of the type of methods you will use in the node class. Rethink your classes. Maybe remove Airplane will be a method in the node class like remove node. Anything that works on the node such as insert or add new, delete, and sort can be added to the node class. You can then reuse this class as you add more classes.

http://docs.oracle.com/javase/tutorial/java/IandI/subclasses.html