Linked lists
are simple and most common data structures. Linked list consists of a group of nodes,
which together represent a sequence.
Following
video, explains about linked list clearly.
Following
are the functions that LinkedList java program provides.
Function
|
Description
|
public
void insertAtEnd(T value)
|
Insert
value at the end of list
|
public int
getLength()
|
Return
number of elements in list
|
public int
getCount(T ele)
|
counts the
number of times a given element occurs in a list.
|
public T
getNth(int n)
|
Get nth
element. Index starts from 0
|
public
boolean deleteList()
|
Delete
list
|
public
boolean deleteFirstNode()
|
Delete
first element.
|
public
boolean insertAtNthPosition(T ele, int index)
|
Insert
element at given index. if index >= length, element inserted at list end.
|
public
LinkedList<T> appendLists(LinkedList<T> list2)
|
Append
list2 to this list.
|
public
LinkedList<T>[] splitList()
|
Split
lists into two equal sublists. If the number of elements is odd, the extra
element should go in the front list.
|
public
LinkedList<T>[] alternateSplit()
|
alternatingSplit()takes
one list and divides up its nodes to make two smaller lists. If the original
list is {a, b, a, b, a}, then one sublist should be {a, a, a} and the other
should be {b, b}.
|
public
LinkedList<T> mergeList(LinkedList<T> list)
|
Merge two
lists.{1, 2, 3} and {7, 13, 1} should yield {1, 7, 2, 13, 3, 1}
|
public
void reverse()
|
Reverse a
list
|
public
boolean deleteLastNode()
|
Delete
last node
|
public
boolean deleteNthNode(int index)
|
Delete nth
node.
|
public
LinkedList<T> sortList()
|
Sort given
new list (uses insertion sort)
|
public
LinkedList<T> mergeSort(LinkedList<T> list)
|
Sort list
using merge sort.
|
public
LinkedList<T> sortAndMergeLists(LinkedList<T> list)
|
Sort this
list and given list and merge them together (Maintains order)
|
public
LinkedList<T> getSortedList(LinkedList<T> list)
|
Return
sorted list.
|
public T
getNthNodeFromLast(int n)
|
Get value
of nth node from last. if n=1, it returns value of first last node, n=2 it
returns value of 2nd last node
|
import java.util.Objects; /** * Generic implementation of single linked list * * @author harikrishna_gurram */ public class LinkedList<T extends Comparable<T>> { private int length = 0; private Node<T> first, last; /** * Create empty linked list */ LinkedList() { first = last = null; } /** * Insert value at the end of list * * @param value */ public void insertAtEnd(T value) { if (first == null) { first = new Node<>(value); last = first; } else { last.nextnode = new Node<>(value); last = last.nextnode; } length++; } /** * Insert value at front of the list. * * @param value */ public void insertAtFirst(T value) { if (first == null) { first = new Node<>(value); last = first; } else { Node<T> node = new Node<>(value); node.nextnode = first; first = node; } length++; } /** * Return number of elements in list * * @return */ public int getLength() { return length; } /** * counts the number of times a given element occurs in a list. */ public int getCount(T ele) { if (first == null) return 0; Node<T> temp = first; int count = 0; while (temp != null) { if (Objects.equals(temp.data, ele)) { count++; } temp = temp.nextnode; } return count; } /** * Get nth element. Index starts from 0 */ public T getNth(int n) { if (first == null) throw new NullPointerException("List is empty"); if (getLength() < n || n < 0) throw new IndexOutOfBoundsException("List index out of bounds"); Node<T> temp = first; int count = 0; while (count < n) { temp = temp.nextnode; count++; } return temp.data; } /** * Delete list. * * @return true,if list deleted successfully, else false. */ public boolean deleteList() { first = null; last = null; length = 0; System.gc(); return true; } /** * Delete first element. */ public boolean deleteFirstNode() { if (first == null) throw new NullPointerException("List is empty"); Node<T> temp = first; first = null; first = temp.nextnode; length--; return true; } /** * Insert element at given index. if index >= length, element inserted at * list end. */ public boolean insertAtNthPosition(T ele, int index) { if (index == 0) { insertAtFirst(ele); return true; } if (index >= length) { insertAtEnd(ele); return true; } int count = 1; Node<T> temp = first; while (count < index) { temp = temp.nextnode; count++; } Node<T> temp1 = new Node<>(ele); temp1.nextnode = temp.nextnode; temp.nextnode = temp1; length++; return true; } /** * Append list2 to this list. * * @param list2 * @return */ public LinkedList<T> appendLists(LinkedList<T> list2) { Objects.nonNull(this); Objects.nonNull(list2); LinkedList<T> newList = new LinkedList<>(); Node<T> temp = this.first; while (temp != null) { newList.insertAtEnd(temp.data); temp = temp.nextnode; } temp = list2.first; while (temp != null) { newList.insertAtEnd(temp.data); temp = temp.nextnode; } return newList; } /** * Split lists into two equal sublists. If the number of elements is odd, * the extra element should go in the front list. */ public LinkedList<T>[] splitList() { Node<T> temp = first; Objects.nonNull(first); int length = getLength(); LinkedList<T> list1 = new LinkedList<>(); LinkedList<T> list2 = new LinkedList<>(); int count = 0; while (temp != null) { if (count > length / 2) break; list1.insertAtEnd(temp.data); temp = temp.nextnode; count++; } while (temp != null) { list2.insertAtEnd(temp.data); temp = temp.nextnode; count++; } @SuppressWarnings("unchecked") LinkedList<T>[] result = new LinkedList[2]; result[0] = list1; result[1] = list2; return result; } /** * AlternatingSplit() that takes one list and divides up its nodes to make * two smaller lists. If the original list is {a, b, a, b, a}, then one * sublist should be {a, a, a} and the other should be {b, b}. */ public LinkedList<T>[] alternateSplit() { LinkedList<T> list1 = new LinkedList<>(); LinkedList<T> list2 = new LinkedList<>(); Node<T> temp = first; while (temp != null) { list1.insertAtEnd(temp.data); temp = temp.nextnode; if (temp != null) { list2.insertAtEnd(temp.data); temp = temp.nextnode; } } @SuppressWarnings("unchecked") LinkedList<T> result[] = new LinkedList[2]; result[0] = list1; result[1] = list2; return result; } /** * Merge two lists.{1, 2, 3} and {7, 13, 1} should yield {1, 7, 2, 13, 3, 1} */ public LinkedList<T> mergeList(LinkedList<T> list) { LinkedList<T> mergedList = new LinkedList<>(); Node<T> temp1 = first; Node<T> temp2 = list.first; while (temp1 != null && temp2 != null) { mergedList.insertAtEnd(temp1.data); mergedList.insertAtEnd(temp2.data); temp1 = temp1.nextnode; temp2 = temp2.nextnode; } Node<T> temp = (temp1 == null) ? temp2 : temp1; while (temp != null) { mergedList.insertAtEnd(temp.data); temp = temp.nextnode; } return mergedList; } /** * Reverse a list */ public void reverse() { if (first == null || getLength() <= 1) return; Node<T> temp = first; reverseList(temp); } private void reverseList(Node<T> head) { Node<T> start = head; Node<T> next = head.nextnode; first = next; if (next.nextnode != null) { reverseList(head.nextnode); } next.nextnode = start; start.nextnode = null; } /** * Delete last node * * @return true, after deleting last node. */ public boolean deleteLastNode() { Objects.nonNull(first); if (first.nextnode == null) { deleteFirstNode(); length--; return true; } Node<T> temp = first; while (temp.nextnode.nextnode != null) { temp = temp.nextnode; } temp.nextnode = null; last = temp; length--; return true; } /** * Delete nth node. * * @param index * @return */ public boolean deleteNthNode(int index) { if (first == null) { throw new NullPointerException("List is empty"); } if (length < index) { throw new IndexOutOfBoundsException("List index out of bounds"); } if (index == 0) { deleteFirstNode(); return true; } if (index == length - 1) { deleteLastNode(); return true; } Node<T> temp = first; for (int i = 0; i < index - 1; i++) { temp = temp.nextnode; } temp.nextnode = temp.nextnode.nextnode; length--; return true; } private void sortedInsert(T ele) { if (first == null) { insertAtFirst(ele); return; } Node<T> temp = first; int count = 0; for (int i = 0; i < length; i++) { if (temp.data.compareTo(ele) > 0) break; temp = temp.nextnode; count++; } insertAtNthPosition(ele, count); } /** * Sort given new list (uses insertion sort) */ public LinkedList<T> sortList() { return getSortedList(this); } /** * Sort list using merge sort. * * @param list * @return */ public LinkedList<T> mergeSort(LinkedList<T> list) { if (list.getLength() > 2) { LinkedList<T>[] lists = list.splitList(); LinkedList<T> left = lists[0]; LinkedList<T> right = lists[1]; LinkedList<T> leftList = mergeSort(left); LinkedList<T> rigthList = mergeSort(right); return leftList.mergeListsforMergeSort(rigthList); } return list; } /** * Merge procedure used by merge sort. * * @param list * @return */ private LinkedList<T> mergeListsforMergeSort(LinkedList<T> list) { LinkedList<T> mergedList = new LinkedList<>(); Node<T> temp1 = this.first; Node<T> temp2 = list.first; while (temp1 != null && temp2 != null) { if (temp1.data.compareTo(temp2.data) < 0) { mergedList.insertAtEnd(temp1.data); temp1 = temp1.nextnode; } else { mergedList.insertAtEnd(temp2.data); temp2 = temp2.nextnode; } } Node<T> temp = temp1; if (temp == null) { temp = temp2; } while (temp != null) { mergedList.insertAtEnd(temp.data); temp = temp.nextnode; } return mergedList; } /** * Sort this list and given list and merge them together (Maintains order) * * @param list * @return */ public LinkedList<T> sortAndMergeLists(LinkedList<T> list) { LinkedList<T> sorted1 = this.sortList(); LinkedList<T> sorted2 = list.sortList(); return sorted1.mergeListsforMergeSort(sorted2); } /** * Return sorted list. * * @param list * @return */ public LinkedList<T> getSortedList(LinkedList<T> list) { LinkedList<T> result = new LinkedList<>(); Node<T> temp = list.first; while (temp != null) { result.sortedInsert(temp.data); temp = temp.nextnode; } return result; } /** * Get value of nth node from last. if n=1, it returns value of first last * node, n-2 it returns value of 2nd last node * * @return */ public T getNthNodeFromLast(int n) { if (n > length || n < 0) throw new IllegalArgumentException( "input should be less than list size " + length + " and greater than zero"); int nthLastNode = (length - n); return getNth(nthLastNode); } /** * Return node at given index * * @param index * @return */ public Node<T> getNthNode(int index) { if (index < 0 || index > length - 1) throw new IllegalArgumentException("index must >0 and < list size " + length); Node<T> temp = first; for (int i = 0; i < index; i++) { temp = temp.nextnode; } return temp; } public String toString() { StringBuilder builder = new StringBuilder(); Node<T> temp = first; if (first == null) return ""; while (temp.nextnode != null) { builder = builder.append(temp.data).append("->"); temp = temp.nextnode; } builder = builder.append(temp.data); return builder.toString(); } private class Node<E> { E data; Node<E> nextnode; Node(E data) { this.data = data; nextnode = null; } } }
Following is
the junit test case for above program.
import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; import org.junit.Before; import org.junit.Test; public class ListTest { private static LinkedList<Integer> tempList; @Before public void setup() { tempList = new LinkedList<>(); tempList.insertAtEnd(10); tempList.insertAtEnd(20); tempList.insertAtEnd(30); tempList.insertAtEnd(40); tempList.insertAtEnd(50); tempList.insertAtEnd(50); tempList.insertAtEnd(10); } @Test public void testInsertAtFirst() { LinkedList<Integer> list = new LinkedList<>(); list.insertAtFirst(10); list.insertAtFirst(20); list.insertAtFirst(30); list.insertAtFirst(40); list.insertAtFirst(50); assertEquals(list.toString(), "50->40->30->20->10"); } @Test public void testInsertAtEnd() { LinkedList<Integer> list = new LinkedList<>(); list.insertAtEnd(10); list.insertAtEnd(20); assertEquals(list.toString(), "10->20"); list.insertAtEnd(30); list.insertAtEnd(40); list.insertAtEnd(50); assertEquals(list.toString(), "10->20->30->40->50"); } @Test public void testGetLength() { LinkedList<Integer> list = new LinkedList<>(); assertEquals(list.getLength(), 0); list.insertAtEnd(10); list.insertAtEnd(20); list.insertAtEnd(30); list.insertAtEnd(40); list.insertAtEnd(50); assertEquals(list.getLength(), 5); assertEquals(list.toString(), "10->20->30->40->50"); } @Test public void testGetCount() { assertEquals(tempList.getCount(10), 2); assertEquals(tempList.getCount(20), 1); assertEquals(tempList.getCount(30), 1); assertEquals(tempList.getCount(40), 1); assertEquals(tempList.getCount(50), 2); } @Test public void testgetNth() { assertTrue(tempList.getNth(0) == 10); assertTrue(tempList.getNth(1) == 20); assertTrue(tempList.getNth(2) == 30); assertTrue(tempList.getNth(3) == 40); assertTrue(tempList.getNth(4) == 50); assertTrue(tempList.getNth(5) == 50); assertTrue(tempList.getNth(6) == 10); } @Test public void testDeleteAtFirst() { assertEquals(tempList.toString(), "10->20->30->40->50->50->10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), "20->30->40->50->50->10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), "30->40->50->50->10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), "40->50->50->10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), "50->50->10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), "50->10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), "10"); tempList.deleteFirstNode(); assertEquals(tempList.toString(), ""); } @Test public void testInsertAtNth() { assertEquals(tempList.toString(), "10->20->30->40->50->50->10"); tempList.insertAtNthPosition(11, 1); assertEquals(tempList.toString(), "10->11->20->30->40->50->50->10"); tempList.insertAtNthPosition(12, 2); assertEquals(tempList.toString(), "10->11->12->20->30->40->50->50->10"); tempList.insertAtNthPosition(13, 3); assertEquals(tempList.toString(), "10->11->12->13->20->30->40->50->50->10"); } @Test public void testAppendLists() { LinkedList<Integer> list1 = new LinkedList<>(); LinkedList<Integer> list2 = new LinkedList<>(); list1.insertAtFirst(30); list1.insertAtFirst(20); list1.insertAtFirst(10); list2.insertAtFirst(60); list2.insertAtFirst(50); list2.insertAtFirst(40); LinkedList<Integer> newList = list1.appendLists(list2); assertEquals(newList.toString(), "10->20->30->40->50->60"); } @Test public void testSplitList() { assertEquals(tempList.toString(), "10->20->30->40->50->50->10"); LinkedList<Integer>[] lists = tempList.splitList(); assertEquals(lists[0].toString(), "10->20->30->40"); assertEquals(lists[1].toString(), "50->50->10"); } @Test public void testAlternateSplit() { assertEquals(tempList.toString(), "10->20->30->40->50->50->10"); LinkedList<Integer>[] lists = tempList.alternateSplit(); assertEquals(lists[0].toString(), "10->30->50->10"); assertEquals(lists[1].toString(), "20->40->50"); } @Test public void testMergeList() { LinkedList<Integer> tempList1 = new LinkedList<>(); LinkedList<Integer> tempList2 = new LinkedList<>(); tempList1.insertAtEnd(0); tempList1.insertAtEnd(2); tempList1.insertAtEnd(4); tempList1.insertAtEnd(6); tempList2.insertAtEnd(1); tempList2.insertAtEnd(3); tempList2.insertAtEnd(5); tempList2.insertAtEnd(7); tempList2.insertAtEnd(9); tempList2.insertAtEnd(11); LinkedList<Integer> result = tempList1.mergeList(tempList2); assertEquals(result.toString(), "0->1->2->3->4->5->6->7->9->11"); } @Test public void testReverse() { LinkedList<Integer> list1 = new LinkedList<>(); list1.insertAtEnd(10); list1.insertAtEnd(20); list1.insertAtEnd(30); list1.insertAtEnd(40); LinkedList<Integer> list2 = new LinkedList<>(); list2.insertAtEnd(10); LinkedList<Integer> list3 = new LinkedList<>(); list3.insertAtEnd(10); list3.insertAtEnd(20); LinkedList<Integer> list4 = new LinkedList<>(); list4.insertAtEnd(10); list4.insertAtEnd(20); list4.insertAtEnd(30); assertEquals(list1.toString(), "10->20->30->40"); assertEquals(list2.toString(), "10"); assertEquals(list3.toString(), "10->20"); assertEquals(list4.toString(), "10->20->30"); list1.reverse(); list2.reverse(); list3.reverse(); list4.reverse(); assertEquals(list1.toString(), "40->30->20->10"); assertEquals(list2.toString(), "10"); assertEquals(list3.toString(), "20->10"); assertEquals(list4.toString(), "30->20->10"); } @Test public void testDeleteLastNode() { LinkedList<Integer> list1 = new LinkedList<>(); LinkedList<Integer> list2 = new LinkedList<>(); LinkedList<Integer> list3 = new LinkedList<>(); LinkedList<Integer> list4 = new LinkedList<>(); list1.insertAtEnd(10); list2.insertAtEnd(10); list2.insertAtEnd(20); list3.insertAtEnd(10); list3.insertAtEnd(20); list3.insertAtEnd(30); list4.insertAtEnd(10); list4.insertAtEnd(20); list4.insertAtEnd(30); list4.insertAtEnd(40); assertEquals(list1.toString(), "10"); assertEquals(list2.toString(), "10->20"); assertEquals(list3.toString(), "10->20->30"); assertEquals(list4.toString(), "10->20->30->40"); list1.deleteLastNode(); list2.deleteLastNode(); list3.deleteLastNode(); list4.deleteLastNode(); assertEquals(list1.toString(), ""); assertEquals(list2.toString(), "10"); assertEquals(list3.toString(), "10->20"); assertEquals(list4.toString(), "10->20->30"); } @Test public void sortedList() { LinkedList<Integer> list = new LinkedList<>(); list.insertAtEnd(1); list.insertAtEnd(10); list.insertAtEnd(5); list.insertAtEnd(15); LinkedList<Integer> list2 = new LinkedList<>(); list2.insertAtEnd(10); LinkedList<Integer> list3 = new LinkedList<>(); LinkedList<Integer> sorted1 = list.sortList(); LinkedList<Integer> sorted2 = tempList.sortList(); LinkedList<Integer> sorted3 = list2.sortList(); LinkedList<Integer> sorted4 = list3.sortList(); assertEquals(sorted1.toString(), "1->5->10->15"); assertEquals(sorted2.toString(), "10->10->20->30->40->50->50"); assertEquals(sorted3.toString(), "10"); assertEquals(sorted4.toString(), ""); } @Test public void testDeleteNthNode() { assertEquals(tempList.toString(), "10->20->30->40->50->50->10"); tempList.deleteNthNode(3); assertEquals(tempList.toString(), "10->20->30->50->50->10"); tempList.deleteNthNode(3); assertEquals(tempList.toString(), "10->20->30->50->10"); tempList.deleteNthNode(3); assertEquals(tempList.toString(), "10->20->30->10"); tempList.deleteNthNode(3); assertEquals(tempList.toString(), "10->20->30"); tempList.deleteNthNode(1); assertEquals(tempList.toString(), "10->30"); tempList.deleteNthNode(1); assertEquals(tempList.toString(), "10"); tempList.deleteNthNode(0); assertEquals(tempList.toString(), ""); } @Test public void testSortAndMergeLists() { LinkedList<Integer> list1 = new LinkedList<>(); LinkedList<Integer> list2 = new LinkedList<>(); list1.insertAtEnd(2); list1.insertAtEnd(6); list1.insertAtEnd(8); list1.insertAtEnd(4); list2.insertAtEnd(1); list2.insertAtEnd(5); list2.insertAtEnd(7); list2.insertAtEnd(3); LinkedList<Integer> mergeList = list1.sortAndMergeLists(list2); assertEquals(mergeList.toString(), "1->2->3->4->5->6->7->8"); mergeList = list2.sortAndMergeLists(list1); assertEquals(mergeList.toString(), "1->2->3->4->5->6->7->8"); mergeList = tempList.sortAndMergeLists(list1); assertEquals(mergeList.toString(), "2->4->6->8->10->10->20->30->40->50->50"); } @Test public void mergeSort() { LinkedList<Integer> list = new LinkedList<>(); list.insertAtEnd(1); list.insertAtEnd(10); list.insertAtEnd(5); list.insertAtEnd(15); LinkedList<Integer> list2 = new LinkedList<>(); list2.insertAtEnd(10); LinkedList<Integer> list3 = new LinkedList<>(); LinkedList<Integer> sorted1 = list.mergeSort(list); LinkedList<Integer> sorted2 = tempList.mergeSort(tempList); LinkedList<Integer> sorted3 = list2.mergeSort(list2); LinkedList<Integer> sorted4 = list3.mergeSort(list3); assertEquals(sorted1.toString(), "1->5->10->15"); assertEquals(sorted2.toString(), "10->10->20->30->40->50->50"); assertEquals(sorted3.toString(), "10"); assertEquals(sorted4.toString(), ""); } @Test public void jumblingTest() { LinkedList<Integer> list1 = new LinkedList<>(); assertEquals(list1.toString(), ""); list1.insertAtEnd(10); list1.insertAtFirst(20); assertEquals(list1.toString(), "20->10"); list1.deleteLastNode(); assertEquals(list1.toString(), "20"); list1.insertAtEnd(30); assertEquals(list1.toString(), "20->30"); list1.deleteFirstNode(); assertEquals(list1.toString(), "30"); list1.insertAtFirst(50); assertEquals(list1.toString(), "50->30"); list1.insertAtFirst(60); assertEquals(list1.toString(), "60->50->30"); list1.deleteNthNode(1); assertEquals(list1.toString(), "60->30"); } @Test public void testGetNthNodeFromLast() { LinkedList<Integer> list1 = new LinkedList<>(); list1.insertAtEnd(10); list1.insertAtEnd(20); list1.insertAtEnd(30); list1.insertAtEnd(40); list1.insertAtEnd(50); list1.insertAtEnd(60); assertTrue(list1.getNthNodeFromLast(1).equals(60)); assertTrue(list1.getNthNodeFromLast(2).equals(50)); assertTrue(list1.getNthNodeFromLast(3).equals(40)); assertTrue(list1.getNthNodeFromLast(4).equals(30)); assertTrue(list1.getNthNodeFromLast(5).equals(20)); assertTrue(list1.getNthNodeFromLast(6).equals(10)); } }
No comments:
Post a Comment