patternjavaMinor
Singly linked list implementation in Java without help of java.util.linkedlist
Viewed 0 times
withoutimplementationutillinkedlisthelpjavasinglylistlinked
Problem
I am learning Java and as a first exercise I tried to implement singly linked list without the help of
Node.java
HeadNode.java
DataItems.java
LinkedList.java
```
public class LinkedList{
HeadNode head;
public LinkedList(){
head = new HeadNode();
}
// insert node at the beginning of the list
public void insertNode(DataItems _data){
Node newNode = new Node();
newNode.setDataItems(_data);
Node nextNode = head.getNextNode();
head.setNextNode(newNode);
newNode.setNextNode(nextNode);
}
// delete node at the beginning of the list
public void deleteNode(){
Node toBeDeletedNode = head.getNextNode();
if(toBeDelet
java.util. I tested my program for basic operations and it seems to work fine. But I still want to know if there are any improvements I could do in terms of design or implementation in OOP.Node.java
public class Node{
// immutable class representing head node of linked list
private DataItems dataItems;
private Node nextNode;
public void setNextNode(Node _nextNode){
this.nextNode=_nextNode;
}
public Node getNextNode(){
return nextNode;
}
public DataItems getDataItems(){
return dataItems;
}
public void setDataItems(DataItems _dataItems){
this.dataItems=_dataItems;
}
}HeadNode.java
public class HeadNode{
// immutable class representing head node of linked list
Node nextNode;
public void setNextNode(Node _nextNode) {
nextNode=_nextNode;
}
public Node getNextNode() {
return nextNode;
}
}DataItems.java
public class DataItems{
private int key;
private String value;
public DataItems(int _key, String _value){
this.key=_key;
this.value=_value;
}
public int getKey() {
return key;
}
public String getValue() {
return value;
}
public String toString() {
return "("+getKey()+","+getValue()+")";
}
}LinkedList.java
```
public class LinkedList{
HeadNode head;
public LinkedList(){
head = new HeadNode();
}
// insert node at the beginning of the list
public void insertNode(DataItems _data){
Node newNode = new Node();
newNode.setDataItems(_data);
Node nextNode = head.getNextNode();
head.setNextNode(newNode);
newNode.setNextNode(nextNode);
}
// delete node at the beginning of the list
public void deleteNode(){
Node toBeDeletedNode = head.getNextNode();
if(toBeDelet
Solution
I've only glanced at your code, but two things stood out.
Immutable
In
Either immutable doesn't mean what you think it does, or this comment is confused. Immutable classes don't change after they've been constructed. They typically have final members so that they can't be assigned to. You
Testing
Rather than rolling your own tests in
A few afterthoughts to add to @Jonas' answer.
Node
At the moment you have a distinction between nodes that have data (
Efficiency
As @Janos pointed out, some of your methods are not very efficient. The one that most struck me was your
Error Checking
Some of your methods can fail, but don't have a method for telling the client. For example,
Immutable
In
HeadNode you have a comment:// immutable class representing head node of linked listEither immutable doesn't mean what you think it does, or this comment is confused. Immutable classes don't change after they've been constructed. They typically have final members so that they can't be assigned to. You
HeadNode class provides bother a getter and a setter for its only field nextNode. This isn't an immutable class.Testing
Rather than rolling your own tests in
main, consider looking into a testing framework like JUnit. It allows you to encapsulate tests for different functionality in a more expressive way, so that you can clearly tell from the test runs what is failing if you introduce bugs.A few afterthoughts to add to @Jonas' answer.
Node
At the moment you have a distinction between nodes that have data (
Node) and nodes that don't have data (HeadNode). Does it really make sense to have a Node that doesn't have a dataitem associated with it? Looking at your code, the answer is probably not, the first thing you do after creating a new Node is to call setDataItems. With that in mind, it would be better to add a constructor to your Node class that takes in a data item, rather than requiring the client to call a member function immediately after construction.Efficiency
As @Janos pointed out, some of your methods are not very efficient. The one that most struck me was your
searchKey method. It relies on your dataAtNodeIndex method which in turn relies on nodeAtIndex. Since your nodeAtIndex always starts from head, you end up searching the list over and over again from the start, going one item further each time until you find they key you're looking for.Error Checking
Some of your methods can fail, but don't have a method for telling the client. For example,
insertNodeAtIndex and deleteNodeAtIndex both return void. They also have ways that they can fail to deliver on their promises and fail silently. If a client calls insertNodeAtIndex(5) when the list only has 3 items, then you have a few options. At the moment, you effectively ignore the request (the client has no way to know that the item hasn't been added to the list). It would be better to at the item to the tail of the list (this fulfils the insert promise). However, it would be better still to throw an exception to indicate to the client that they've made an invalid request and that the item hasn't been inserted into the list.Code Snippets
// immutable class representing head node of linked listContext
StackExchange Code Review Q#151995, answer score: 4
Revisions (0)
No revisions yet.