Why Linked Lists?
The linked list is the basis for a number of problems regarding the handling of dynamic data.Kinds of Linked List
There are three basic kinds of linked list: singly linked lists, doubly linked lists, and circular linked lists. Let's discuss singly linked lists in this post.Singly Linked Lists
Each data element in the list has a link (a pointer or reference) to the element that follows it in the
list. The first element in a singly linked list is referred to as the head of the list. The last element in such a list is called the tail of the list and has an empty or null link.
 |
| Singly linked list |
Because the links in a singly linked list consist only of next pointers (or references), the list can be traversed only in the forward direction. Therefore a complete traversal of the list must begin with the first element. In other words, you need a pointer or reference to the first element of a list to locate all the elements in the list.
Basic Linked List Operations
The LinkedList element is represented in LinkedListNode private class and LinkedList functionalities are represented in LinkedList class. This class is generic.
public class LinkedList<E> {
private class LinkedListNode {
private E data;
private LinkedListNode next;
private LinkedListNode() {
this.data = null;
this.next = null;
}
private LinkedListNode(E data) {
this.data = data;
this.next = null;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public LinkedListNode getNext() {
return next;
}
public void setNext(LinkedListNode next) {
this.next = next;
}
}
private LinkedListNode firstNode;
private LinkedListNode lastNode;
private int size;
// Empty list constructor
public LinkedList() {
this.firstNode = new LinkedListNode();
this.lastNode = this.firstNode;
size = 0;
}
// Construct a list with a single node
public LinkedList(E data) {
this();
this.addStart(data);
}
// Construct a list with an array of nodes
public LinkedList(E[] inputList) {
this();
for (E input : inputList) {
this.addStart(input);
}
}
}
Adding
Following is Java code to add an input node to the beginning of a LinkedList (addStart), to specific index (addAt), and to the end of (addLast).
// Add a node to the beginning of a list
public void addStart(E input) {
LinkedListNode node = new LinkedListNode(input);
// if the list is empty
if (this.firstNode.getData() == null) {
this.firstNode = node;
this.lastNode = node;
} else {
LinkedListNode previousFirstNode = this.firstNode;
this.firstNode = node;
node.setNext(previousFirstNode);
}
this.size++;
}
// Add a node to specific location
public void addAt(E input, int index) {
LinkedListNode node = new LinkedListNode(input);
if (index < this.size) {
LinkedListNode right = this.firstNode;
LinkedListNode left = new LinkedListNode();
for (int position = 0; position < index; position++) {
left = right;
right = right.getNext();
}
left.setNext(node);
node.setNext(right);
this.size++;
}
}
// Add a node to the end of a list
public void addLast(E input) {
LinkedListNode node = new LinkedListNode(input);
// if the list is empty
if (this.firstNode.getData() == null) {
this.firstNode = node;
this.lastNode = node;
} else {
this.lastNode.setNext(node);
this.lastNode = node;
}
this.size++;
}
Removing
To remove an object from a LinkedList:
// Delete a node from the linked list
public boolean remove(E inputData) {
boolean wasDeleted = false;
LinkedListNode currentNode = this.firstNode;
if (this.size == 0) {
return wasDeleted;
}
// If we are removing the first node
if (inputData.equals(currentNode.getData())) {
// If there is only one node in the list
if (currentNode.getNext() == null) {
this.firstNode.setData(null);
this.firstNode = new LinkedListNode();
this.lastNode = this.firstNode;
this.size--;
return true;
}
currentNode.setData(null);
currentNode = currentNode.getNext();
this.firstNode = currentNode;
this.size--;
return true;
}
// If we are not removing the first node
while (true) {
// If end of list, stop
if (currentNode == null) {
wasDeleted = false;
break;
}
// Check if the data of the next is what we're looking for
LinkedListNode nextNode = currentNode.getNext();
if (nextNode != null) {
if (inputData.equals(nextNode.getData())) {
// Found the right one, loop around the node
LinkedListNode nextNextNode = nextNode.getNext();
currentNode.setNext(nextNextNode);
nextNode = null;
wasDeleted = true;
break;
}
}
currentNode = currentNode.getNext();
}
if (wasDeleted) {
this.size--;
}
return wasDeleted;
}
Searching
To find index of a specific node in a LinkedList. Note that this returns index of the first occurance of anode:
// Find a node in the linked list
public int indexOf(E inputData) {
int position = -1;
LinkedListNode currentNode = this.firstNode;
for (int i = 0; i < this.size; i++) {
if (currentNode.getData().equals(inputData)) {
position = i;
break;
}
currentNode = currentNode.getNext();
}
return position;
}
Also, we can get an element at a specific position
// Get the element at a specific position
public E elementAt(int inputPosition) {
if (inputPosition >= this.size || inputPosition < 0) {
return null;
}
LinkedListNode currentNode = this.firstNode;
for (int position = 0; position < inputPosition; position++) {
currentNode = currentNode.getNext();
}
return currentNode.getData();
}
We can find elements between the mth to nth position in a LinkedList:
// find the mth-to-nth element of the list
public Object[] find(int startPosition, int endPosition) {
if (startPosition <= this.size && endPosition <= this.size
&& startPosition < endPosition) {
Object[] result = new Object[endPosition - startPosition + 1];
LinkedListNode currentNode = this.firstNode;
int counter = 0;
for (int i = 0; i <= endPosition; i++) {
if (i >= startPosition) {
result[counter] = currentNode.getData();
counter++;
}
currentNode = currentNode.getNext();
}
return result;
}
return null;
}
To Find the last mth element of a LinkedList:
// find the mth-to-last element of the list
public Object[] findLast(int m) {
if (m <= this.size) {
Object[] result = new Object[m];
int elementAt = this.size - m;
LinkedListNode currentNode = this.firstNode;
int counter = 0;
for (int i = 0; i < this.size; i++) {
if (i >= elementAt) {
result[counter] = currentNode.getData();
counter++;
}
currentNode = currentNode.getNext();
}
return result;
}
return null;
}
Size
To get the LinkedList size:
// Get the size of the list
public int getSize() {
return this.size;
}
Evaluation
Complexity Analysis
| Functionality | Complexity |
|---|---|
| Insert/delete at beginning | O(1) |
| Insert/delete at end | last element is unknown: O(n) last element is known: O(1) |
| Insert/delete in middle | search time+O(1) |
Advantages
- It is a dynamic data structure. The memory is created at run time while running a program.
- Insertion and deletion nodes operations are very easy in linked list. We can insert node and delete node easily.
- Linear data structures such as stacks and queues can be easily implemented using linked list.
- The access time is faster in linked list and it can be expanded in constant time without memory overhead.
Disadvantages
- Wastage of memory takes place in linked list as pointers requires extra memory for storage.
- In Linked list no random access is given to user, we have to access each node sequentially.
- In linked list, it takes a lot of time to access an element as individual nodes are not stored in contiguous memory allocations.
- Reverse traversing is very difficult in linked list. In case if we are using singly linked list then it is very difficult to traverse linked list from end. If using doubly linked list then though it becomes easier to traverse from end but still it increases again storage space for back pointer.
Source Code
public class LinkedList<E> {
private class LinkedListNode {
private E data;
private LinkedListNode next;
private LinkedListNode() {
this.data = null;
this.next = null;
}
private LinkedListNode(E data) {
this.data = data;
this.next = null;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public LinkedListNode getNext() {
return next;
}
public void setNext(LinkedListNode next) {
this.next = next;
}
}
private LinkedListNode firstNode;
private LinkedListNode lastNode;
private int size;
// Empty list constructor
public LinkedList() {
this.firstNode = new LinkedListNode();
this.lastNode = this.firstNode;
size = 0;
}
// Construct a list with a single node
public LinkedList(E data) {
this();
this.addStart(data);
}
// Construct a list with an array of nodes
public LinkedList(E[] inputList) {
this();
for (E input : inputList) {
this.addStart(input);
}
}
// Add a node to the beginning of a list
public void addStart(E input) {
LinkedListNode node = new LinkedListNode(input);
// if the list is empty
if (this.firstNode.getData() == null) {
this.firstNode = node;
this.lastNode = node;
} else {
LinkedListNode previousFirstNode = this.firstNode;
this.firstNode = node;
node.setNext(previousFirstNode);
}
this.size++;
}
// Add a node to specific location
public void addAt(E input, int index) {
LinkedListNode node = new LinkedListNode(input);
if (index < this.size) {
LinkedListNode right = this.firstNode;
LinkedListNode left = new LinkedListNode();
for (int position = 0; position < index; position++) {
left = right;
right = right.getNext();
}
left.setNext(node);
node.setNext(right);
this.size++;
}
}
// Add a node to the end of a list
public void addLast(E input) {
LinkedListNode node = new LinkedListNode(input);
// if the list is empty
if (this.firstNode.getData() == null) {
this.firstNode = node;
this.lastNode = node;
} else {
this.lastNode.setNext(node);
this.lastNode = node;
}
this.size++;
}
// Get the size of the list
public int getSize() {
return this.size;
}
// Find a node in the linked list
public int indexOf(E inputData) {
int position = -1;
LinkedListNode currentNode = this.firstNode;
for (int i = 0; i < this.size; i++) {
if (currentNode.getData().equals(inputData)) {
position = i;
break;
}
currentNode = currentNode.getNext();
}
return position;
}
// Delete a node from the linked list
public boolean remove(E inputData) {
boolean wasDeleted = false;
LinkedListNode currentNode = this.firstNode;
if (this.size == 0) {
return wasDeleted;
}
// If we are removing the first node
if (inputData.equals(currentNode.getData())) {
// If there is only one node in the list
if (currentNode.getNext() == null) {
this.firstNode.setData(null);
this.firstNode = new LinkedListNode();
this.lastNode = this.firstNode;
this.size--;
return true;
}
currentNode.setData(null);
currentNode = currentNode.getNext();
this.firstNode = currentNode;
this.size--;
return true;
}
// If we are not removing the first node
while (true) {
// If end of list, stop
if (currentNode == null) {
wasDeleted = false;
break;
}
// Check if the data of the next is what we're looking for
LinkedListNode nextNode = currentNode.getNext();
if (nextNode != null) {
if (inputData.equals(nextNode.getData())) {
// Found the right one, loop around the node
LinkedListNode nextNextNode = nextNode.getNext();
currentNode.setNext(nextNextNode);
nextNode = null;
wasDeleted = true;
break;
}
}
currentNode = currentNode.getNext();
}
if (wasDeleted) {
this.size--;
}
return wasDeleted;
}
// Get the element at a specific position
public E elementAt(int inputPosition) {
if (inputPosition >= this.size || inputPosition < 0) {
return null;
}
LinkedListNode currentNode = this.firstNode;
for (int position = 0; position < inputPosition; position++) {
currentNode = currentNode.getNext();
}
return currentNode.getData();
}
// find the mth-to-nth element of the list
public Object[] find(int startPosition, int endPosition) {
if (startPosition <= this.size && endPosition <= this.size
&& startPosition < endPosition) {
Object[] result = new Object[endPosition - startPosition + 1];
LinkedListNode currentNode = this.firstNode;
int counter = 0;
for (int i = 0; i <= endPosition; i++) {
if (i >= startPosition) {
result[counter] = currentNode.getData();
counter++;
}
currentNode = currentNode.getNext();
}
return result;
}
return null;
}
// find the mth-to-last element of the list
public Object[] findLast(int m) {
if (m <= this.size) {
Object[] result = new Object[m];
int elementAt = this.size - m;
LinkedListNode currentNode = this.firstNode;
int counter = 0;
for (int i = 0; i < this.size; i++) {
if (i >= elementAt) {
result[counter] = currentNode.getData();
counter++;
}
currentNode = currentNode.getNext();
}
return result;
}
return null;
}
// Return a string representation of the list
@Override
public String toString() {
LinkedListNode currentNode = this.firstNode;
StringBuffer buffer = new StringBuffer();
buffer.append("{");
for (int i = 0; currentNode != null; i++) {
if (i > 0) {
buffer.append(",");
}
E data = currentNode.getData();
buffer.append(data == null ? "" : data);
currentNode = currentNode.getNext();
}
buffer.append("}");
return buffer.toString();
}
public Object[] iterator() {
Object[] list = new Object[this.size];
LinkedListNode currentNode = this.firstNode;
for (int i = 0; i < this.size; i++) {
list[i] = currentNode.getData();
currentNode = currentNode.getNext();
}
return list;
}
}
JUnit Test
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class LinkedListTest<E> {
@Test
public void testLinkedList() {
LinkedList<Integer> ll = new LinkedList<Integer>();
assertTrue(0 == ll.getSize());
}
@Test
public void testLinkedListObject() {
LinkedList<Integer> ll = new LinkedList<Integer>(150);
assertTrue(1 == ll.getSize());
}
@Test
public void testLinkedListObjectArray() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
assertTrue(4 == ll.getSize());
}
@Test
public void testAddStart() {
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.addStart(120);
assertTrue(0 == ll.indexOf(120));
}
@Test
public void testAddAt() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
ll.addAt(120, 1);
assertTrue(1 == ll.indexOf(120));
}
@Test
public void testAddLast() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
ll.addLast(120);
assertTrue(4 == ll.indexOf(120));
}
@Test
public void testGetSize() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
assertTrue(4 == (Integer) ll.getSize());
}
@Test
public void testIndexOf() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
assertTrue(1 == ll.indexOf(20));
}
@Test
public void testRemove() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
assertTrue(Boolean.TRUE == ll.remove(15));
}
@Test
public void testElementAt() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
assertTrue(350 == (Integer) ll.elementAt(0));
}
@Test
public void testFind() {
Integer[] numbers = { 10, 15, 20, 350, 50, 40, 100, 200 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
Object[] llFind = ll.find(2, 5);
assertTrue(4 == llFind.length);
assertTrue(40 == (Integer) llFind[0]);
assertTrue(50 == (Integer) llFind[1]);
assertTrue(350 == (Integer) llFind[2]);
assertTrue(20 == (Integer) llFind[3]);
}
@Test
public void testfindLast() {
Integer[] numbers = { 10, 15, 20, 350, 50, 40, 100, 200, 54, 87, 23,
76, 34, 54, 56, 57, 68, 7, 54 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
Object[] llFind = ll.findLast(5);
assertTrue(5 == llFind.length);
assertTrue(50 == (Integer) llFind[0]);
assertTrue(350 == (Integer) llFind[1]);
assertTrue(20 == (Integer) llFind[2]);
assertTrue(15 == (Integer) llFind[3]);
assertTrue(10 == (Integer) llFind[4]);
}
@Test
public void testToString() {
Integer[] numbers = { 10, 15, 20, 350 };
LinkedList<Integer> ll = new LinkedList<Integer>(numbers);
assertTrue(ll.toString().length() > 0);
}
}
References
The Linked List in Java in danielacton blogLinked List on Wikipedia
No comments:
Post a Comment