different ways to implement singly linked list

[john hog]

so I had a question on stackoverflow on 2 different ways to implement a linked list and I sort of got my answer, but I need reassurance.

When creating a linked list class why do some people make 'head' the start of the list, while others make 'head' the current node of the list. In other words, in the first case head will always be the first position in the list, and so when implementing methods you must traverse the list. In the second case, head will always be the last node entered, so if I have 10 nodes than head is the 10th node, and when you add to it, you dont have to traverse the list.

I am so confused on why there exists these 2 different ways and which one to use, mainly for interviews. I am on day 3 of watching linked list videos over and over again and every tutorial does it differently and it is throwing me off. Also why do some singly linked lists have a head AND tail while most only have a head. I am currently viewing like 10 different linked list and they are all different..

[fred rosenberger]

Everything in computer science involves trade-offs. having a 'head' and a 'tail' involves (slightly) more memory, more complexity, and more maintenance, but gives you flexibility in how you use your list.

Having the head always point to the last element entered speeds up the insertion, but at the cost of not preserving the order - i.e. you now have a LIFO rather than a FIFO. That may be OK for some applications, but not for others.

Which to use always depends on the specific case where you will be needing it - there is no "THIS is ALWAYS the right way to do it" answer in CS, ever.

[john hog]

thanks your use of FIFO and LIFO cleared things up

[Campbell Ritchie]

And welcome to the Ranch

[john hog]

thanks, i just finished my implementation can anyone take a look and see if its missing anything? edge cases/etc. I am learning in prep for interviews so it must be presentable

public class MyLinkedList<T> {

	private LinkNode<T> head;
	private int size;

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

	public void display() {
		if (head == null) {
			System.out.println("empty list");
		} else {
			LinkNode<T> current = head;
			while (current != null) {
				System.out.println(current.toString());
				current = current.getNext();
			}
		}

	}

	public  void reverse() {
		if (head == null) {
			System.out.println("empty list");
		} else {
			LinkNode<T> previous = null;
			LinkNode<T> current = head;
			LinkNode<T> next = null;
			while (current != null) {
				next = current.getNext();
				current.setNext(previous);
				previous = current;					
				current = next;
			}		
			head=previous;
		}	
	}

	public void addEnd(T data) {
		if (head == null) {
			head = new LinkNode<T>(data, head);
		} else {
			LinkNode<T> current = head;
			while (current.getNext() != null) {
				current = current.getNext();
			}
			LinkNode<T> newNode = new LinkNode<T>(data, null);
			current.setNext(newNode);
			size++;
		}
	}

	public void addFront(T data) {
		head = new LinkNode<T>(data, head);
		size++;
	}

	public void removeEnd() {
		if (head == null) {
			System.out.println("empty list");
		} else {
			LinkNode<T> current = head;
			LinkNode<T> previous = head;
			while (current.getNext() != null) {
				previous = current;
				current = current.getNext();
			}
			previous.setNext(null);
			size--;
		}
	}

	public void removeFront() {
		if (head == null) {
			System.out.println("empty list");
		} else {
			head = head.getNext();
		}
		size--;
	}

	public void removeNode(T data) {
		if (head == null) {
			System.out.println("empty list");

		} else {
			LinkNode<T> current = head;
			LinkNode<T> previous = head;
			while (current.getData() != data) {
				previous = current;
				current = current.getNext();
			}
			if (current == head) {
				head = head.getNext();
			}
			previous.setNext(current.getNext());
		}
		size--;
	}

	public LinkNode<T> getNode(T data) {
		LinkNode<T> current = head;
		if (head == null) {
			System.out.println("empty list");
			return null;
		} else {
			while (current.getData() != data) {
				if (current.getNext() == null) {
					System.out.println("not found");
					return null;
				}
			}
		}
		return current;
	}

	private static class LinkNode<T> {
		T data;
		LinkNode<T> next;

		private LinkNode(T data, LinkNode<T> next) {
			this.data = data;
			this.next = next;
		}

		public T getData() {
			return data;
		}

		public void setData(T data) {
			this.data = data;
		}

		public LinkNode<T> getNext() {
			return next;
		}

		public void setNext(LinkNode<T> node) {
			this.next = node;
		}

		public String toString() {
			return ("\nData: " + data);

		}

	}

	public static void main(String[] args) {
		MyLinkedList<String> list = new MyLinkedList<String>();
		list.addEnd("a");
		list.addEnd("aaa");
		list.addEnd("aaaaaa");
		list.reverse();
		list.display();

	}

}

[Scott Winterbourne]

john hog wrote: can anyone take a look and see if its missing anything? edge cases/etc. I am learning in prep for interviews so it must be presentable

A friend of mine got this same question and I am trying to work on it myself in case I get something similar during an interview.

How did this implementation turn out?

Thanks,