Have you ever used a LinkedList implementation on the job?
Useless linked list in Java?
Videos
I have been working as a swe for 1 year now, mostly with Java and Spring framework. And not once have I implemented or seen an implementation of a LinkedList on the codebase. I was wondering, what are some real use cases you have seen with LinkedLists?
Hey, so I'm currently in my second semester of comp sci and learning Java. Right now they have me making my own list(singly linked list) class which is only capable of holding one type of object. Will it ever be practical to make my own linked list in java, because from my understanding java.util.LinkedList is just a doubly linked list? Or am I coding this to understand the concept?
If you're actually building a real system, then yes, you'd typically just use the stuff in the standard library if what you need is available there. That said, don't think of this as a pointless exercise. It's good to understand how things work, and understanding linked lists is an important step towards understanding more complex data structures, many of which don't exist in the standard libraries.
There are some differences between the way you're creating a linked list and the way the Java collections API does it. The Collections API is trying to adhere to a more complicated interface. The Collections API linked list is also a doubly linked list, while you're building a singly linked list. What you're doing is more appropriate for a class assignment.
With your LinkedList class, an instance will always be a list of at least one element. With this kind of setup you'd use null for when you need an empty list.
Think of next as being "the rest of the list". In fact, many similar implementations use the name "tail" instead of "next".
Here's a diagram of a LinkedList containing 3 elements:
Note that it's a LinkedList object pointing to a word ("Hello") and a list of 2 elements. The list of 2 elements has a word ("Stack") and a list of 1 element. That list of 1 element has a word ("Overflow") and an empty list (null). So you can treat next as just another list that happens to be one element shorter.
You may want to add another constructor that just takes a String, and sets next to null. This would be for creating a 1-element list.
To append, you check if next is null. If it is, create a new one element list and set next to that.
next = new LinkedList(word);
If next isn't null, then append to next instead.
next.append(word);
This is the recursive approach, which is the least amount of code. You can turn that into an iterative solution which would be more efficient in Java*, and wouldn't risk a stack overflow with very long lists, but I'm guessing that level of complexity isn't needed for your assignment.
* Some languages have tail call elimination, which is an optimization that lets the language implementation convert "tail calls" (a call to another function as the very last step before returning) into (effectively) a "goto". This makes such code completely avoid using the stack, which makes it safer (you can't overflow the stack if you don't use the stack) and typically more efficient. Scheme is probably the most well known example of a language with this feature.
What you have coded is not a LinkedList, at least not one that I recognize. For this assignment, you want to create two classes:
LinkNode
LinkedList
A LinkNode has one member field for the data it contains, and a LinkNode reference to the next LinkNode in the LinkedList. Yes, it's a self referential data structure. A LinkedList just has a special LinkNode reference that refers to the first item in the list.
When you add an item in the LinkedList, you traverse all the LinkNode's until you reach the last one. This LinkNode's next should be null. You then construct a new LinkNode here, set it's value, and add it to the LinkedList.
public class LinkNode {
String data;
LinkNode next;
public LinkNode(String item) {
data = item;
}
}
public class LinkedList {
LinkNode head;
public LinkedList(String item) {
head = new LinkNode(item);
}
public void add(String item) {
//pseudo code: while next isn't null, walk the list
//once you reach the end, create a new LinkNode and add the item to it. Then
//set the last LinkNode's next to this new LinkNode
}
}