LinkedList in Java and some of its common methods

Linked List

Tags: data-structure, data, structure, programming, linkedlist, java

What is a LinkedList

Linked List is a part of the Collection framework present in java.util package. This class is an implementation of the LinkedList data structure which is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. It also has a few disadvantages like the nodes cannot be accessed directly instead we need to start from the head and follow through the link to reach a node we wish to access. By LinkedList in Java (geeksforgeeks.org)

How Does LinkedList work Internally? Since a LinkedList acts as a dynamic array and we do not have to specify the size while creating it, the size of the list automatically increases when we dynamically add and remove items. And also, the elements are not stored continuously. Therefore, there is no need to increase the size. Internally, the LinkedList is implemented using the doubly linked list data structure. The main difference between a normal linked list and a doubly LinkedList is that a doubly linked list contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list. By LinkedList in Java (geeksforgeeks.org)

LinkedList implementation in Java

Before starting with the linked list we will first need a class [ "Node" ] that has two attributes:

  • [ "data" ]: will hold the value
  • [ "next" ]: it will point to the next [ "Node" ] if exist.
1public class Node { 2 int data; 3 Node next; 4 5 public Node(int data) { 6 this.data = data; 7 next = null; 8 } 9}

then we will start with building the basic needs of the linked List.

1public class MyLinkedList { 2 // Will point at the first `Node` that holds the value and the next `Node` if exist 3 Node head; 4 // Will keep track of the elements on the linkedList 5 private int elementsCount; 6 7 // When been called it will initialize both `head` to point at `null` and `elementsCount` to `0` 8 public MyLinkedList() { 9 head = null; 10 elementsCount = 0; 11 } 12 13 // To check whether the linkedList is empty or not 14 boolean isEmpty() { 15 return (elementsCount == 0); 16 } 17 18 // returns the `elementsCount` 19 int count() { 20 return elementsCount; 21 } 22}
  • [ "head" ]: an attribute that will point at the first [ "Node" ] that holds the value and the next [ "Node" ] if exist.
  • [ "elementsCount" ]: a private integer that will keep track of the elements (nodes) on the LinkedList.
  • [ "MyLinkedList" ]: a constructor when called will initialize both [ "head" ] to point at [ "null" ] and [ "elementsCount" ] to [ "0" ].
  • [ "isEmpty" ]: A method that will return a boolean to check whether the LinkedList is empty or not.
  • [ "count" ]: A method that will return the elements (nodes) count [ "elementsCount" ].

Insert at the start of the LinkedList

1int insertFirst(int data) { 2 // Store `data` in a new object `newNode` with type of `Node` and its `newNode.next` = `null` 3 Node newNode = new Node(data); 4 5 // Check if the linked list is empty 6 if (isEmpty()) { 7 // Assign the attribute `head` to the new `newNode` 8 head = newNode; 9 } else { 10 // Assign the `newNode,next` to point at the old node that `head` point to 11 newNode.next = head; 12 13 // Assign the attribute `head` to the new `newNode` 14 head = newNode; 15 } 16 17 // Increment the value of `elementsCount` by one 18 elementsCount++; 19 20 return newNode.data; 21}
  • In this method, it will accept the [ "data" ] and point at the in a new object [ "newNode" ] with the type of [ "Node" ] and its [ "newNode.next" ] = [ "null" ].

  • We will first check if the linked list is empty [ "isEmpty" ]:

  • If true then we will assign the attribute [ "head" ] to the new [ "newNode" ], else if false then that means that the attribute [ "head" ] already has a value.

  • Then we will change the [ "newNode.next" ] to point at the node (old head) that the attribute [ "head" ] points to and then make the [ "head" ] attribute point at the new [ "newNode" ].

  • Finally, we will increment the value of [ "elementsCount" ] by one and return the [ "data" ].

Example for inserting first if the Linked list is not empty

1# (1) 2# head 3# \ 4# \ 5# \ 6# -------------- -------------- -------------- 7# | value | next | | value | next-|---->| value | next-|----> null 8# ------------|- -------------- -------------- ^ 9# newNode | oldNode otherNode | 10# --------------------------------------------------- 11# 12# (2) 13# head 14# \ 15# \ 16# \ 17# -------------- -------------- -------------- 18# | value | next-|---->| value | next-|---->| value | next-|----> null 19# -------------- -------------- -------------- 20# newNode oldNode otherNode 21# 22# (3) 23# head 24# / 25# / 26# / 27# -------------- -------------- -------------- 28# | value | next-|---->| value | next-|---->| value | next-|----> null 29# -------------- -------------- -------------- 30# newNode oldNode otherNode

Insert at the end of the LinkedList

1int insertLast(int data) { 2 // Store `data` in a new object `newNode` with type of `Node` and its `newNode.next` = `null` 3 Node newNode = new Node(data); 4 5 // Check if the linked list is empty 6 if (isEmpty()) { 7 // Assign the attribute `head` to the new `newNode` 8 head = newNode; 9 } else { 10 // Store the current node which in this case we will be the attribute `head` in `tempNode` 11 Node tempNode = head; 12 13 // Keep looping and assigning `tempNode` to `tempNode.next` until we get to the last element where `tempNode.next` = `null` 14 while (tempNode.next != null) { 15 tempNode = tempNode.next; 16 } 17 18 // Assigning the `tempNode.next` to the `newNode` instead of null 19 tempNode.next = newNode; 20 } 21 22 // Increment the value of `elementsCount` by one 23 elementsCount++; 24 return newNode.data; 25}
  • In this method, it will accept the [ "data" ] and use it to build a new object [ "newNode" ] with the type of [ "Node" ] and its [ "newNode.next" ] = [ "null" ].

  • We will first check if the linked list is empty [ "isEmpty" ]:

  • If true then we will change the attribute [ "head" ] to the new [ "newNode" ], else if false then that means that the attribute [ "head" ] already has a value.

  • We will use the variable [ "tempNode" ] to point at the current node which in this case we will be the attribute [ "head" ].

  • Then we will need to go to the last [ "Node" ] we can achieve that by using a while loop through the linked list.

  • We will keep looping and assigning it to the next node until we hit the last element by checking if [ "tempNode.next" ] = [ "null" ].

  • And When we hit the last node we will change its next attribute [ "tempNode.next" ] to point at the new node [ "newNode" ].

  • Finally, we will increment the value of [ "elementsCount" ] by one and return the [ "data" ].

Example for inserting at the end of the Linked list is not empty

1# (1) 2# head 3# \ -------------- 4# \ | value | next-|----> null 5# \ ------------- ^ 6# \ newNode | 7# \ | 8# \ | 9# \ | 10# -------------- -------------- -------------- -------------- -------------- | 11# | value | next-|---->| value | next-|---->| value | next-|---->| value | next-|---->| value | next-|------------------------- 12# -------------- -------------- -------------- -------------- -------------- 13# Node 1 Node 2 Node 3 Node 4 Node 5 14# currently 15# (the last node) 16# (2) 17# head 18# \ -------------- 19# \ | value | next-|----> null 20# \ -------------- 21# \ / newNode 22# \ / currently 23# \ / (the new last node) 24# \ / 25# -------------- -------------- -------------- -------------- ------------/- 26# | value | next-|---->| value | next-|---->| value | next-|---->| value | next-|---->| value | next | 27# -------------- -------------- -------------- -------------- -------------- 28# Node 1 Node 2 Node 3 Node 4 Node 5

Remove from the first of the LinkedList

1int removeFirst() { 2 // Check if linked list is empty 3 if (isEmpty()) { 4 // throw new Exception("LinkedList is empty!"); 5 System.err.println("LinkedList is empty!"); 6 System.exit(-1); 7 } 8 9 // Store the value of the deleted node 10 int removedNodeValue; 11 12 // Check if there is only node 13 if (head.next == null) { 14 // Assign `removedNodeValue` to `head.data` to return it 15 removedNodeValue = head.data; 16 // reset `head` and its attributes 17 head.next = null; 18 head.data = 0; 19 head = null; 20 } else { 21 // Assign `tempRemovedNode` to point at `head` to remove it 22 Node tempRemovedNode = head; 23 // Assign `removedNodeValue` to `head.data` to return it 24 removedNodeValue = head.data; 25 // Assign head to point at the second node 26 head = head.next; 27 28 // Reset `tempRemovedNode` values 29 // tempRemovedNode.next = null; 30 // tempRemovedNode.data = 0; 31 tempRemovedNode = null; 32 } 33 34 // Decrement the value of `elementsCount` by one 35 elementsCount--; 36 37 // Return `removedNodeValue 38 return removedNodeValue; 39}
  • First, we will check if the linked list is empty.
  • if true we will exist and we will print an error or we can throw an exception.
  • Then we will point at the value of the deleted node.
  • After that Check, if there is only one node.
  • And assigning [ "removedNodeValue" ] to [ "head.data" ] to return it.
  • And reset [ "head" ] and its attributes.
  • Then assign [ "tempRemovedNode" ] to point at [ "head" ] to remove it.
  • And assigning [ "removedNodeValue" ] to [ "head.data" ] to return it.
  • And assigning head to point at the second node.
  • Then Reset [ "tempRemovedNode" ] values.
  • And then we decrement the value of [ "elementsCount" ] by one.
  • Finally, we return `removedNodeValue.

Example for removing from the first of the linked list if the Linked list is not empty

1# (1) 2# head 3# / 4# / 5# / 6# -------------- -------------- -------------- 7# | value | next-|---->| value | next-|---->| value | next-|----> null 8# -------------- -------------- -------------- 9# newNode oldNode otherNode 10# 11# (2) 12# head 13# \ 14# \ 15# \ 16# -------------- -------------- -------------- 17# | value | next-|---->| value | next-|---->| value | next-|----> null 18# ------------|- -------------- -------------- ^ 19# newNode | oldNode otherNode | 20# | | 21# --------------------------------------------------- 22# 23# (3) 24# head 25# \ 26# \ 27# \ 28# -------------- -------------- -------------- 29# | value | next | | value | next-|---->| value | next-|----> null 30# ------------|- -------------- -------------- ^ 31# newNode | oldNode otherNode | 32# ----------------------------------------------------

Remove from the end of the LinkedList

1int removeLast() { 2 // Check if linked list is empty 3 if (isEmpty()) { 4 // throw new Exception("LinkedList is empty!"); 5 System.err.println("LinkedList is empty!"); 6 System.exit(-1); 7 } 8 9 // Store the value of the deleted node 10 int removedNodeValue; 11 12 // Check if there is only node 13 if (head.next == null) { 14 // Assign `removedNodeValue` to `head.data` to return it 15 removedNodeValue = head.data; 16 // Assign `head` to point at `null` 17 head = null; 18 } else { 19 // Initially we will point at the first node `head` in it 20 Node tempNode = head; 21 // Using `tempRemovedNode` to point at the node in the position before the desired index to reset it 22 Node tempRemovedNode; 23 24 // Keep looping `tempNode.next.next` not equal `null` (the node before the last one) 25 while (tempNode.next.next != null) { 26 // Assign the node before the last one `tempNode.next` to `tempNode` instead of pointing at the last node 27 tempNode = tempNode.next; 28 } 29 30 // Assign `removedNodeValue` to `head.data` to return it 31 removedNodeValue = tempNode.next.data; 32 // Assign `tempRemovedNode` to point the node that will be removed to reset it 33 tempRemovedNode = tempNode.next; 34 // Assign `tempNode` to point at `null` instead of the removed node 35 tempNode.next = null; 36 37 // Reset the `tempNode` (old last node) 38 // tempRemovedNode.next = null; 39 // tempRemovedNode.data = 0; 40 tempRemovedNode = null; 41 } 42 43 // Decrement the value of `elementsCount` by one 44 elementsCount--; 45 46 // Return `removedNodeValue 47 return removedNodeValue; 48}
  • First, we will check if the linked list is empty.
  • If true we will exist and we will print an error or we can throw an exception.
  • Then we will point at the value of the deleted node.
  • After that Check, if there is only one node.
  • And assigning [ "removedNodeValue" ] to [ "head.data" ] to return it.
  • And assigning [ "head" ] to point at [ "null" ].
  • We will use [ "tempNode" ] to point at the node before the last one when we find it, Initially, we will point at the first node [ "head" ] in it.
  • And we will keep looping [ "tempNode.next.next" ] not equal [ "null" ] (the node before the last one).
  • And assigning the node before the last one [ "tempNode.next" ] to [ "tempNode" ] instead of pointing at the last node.
  • And assigning [ "removedNodeValue" ] to [ "head.data" ] to return it, and Assign [ "tempRemovedNode" ] to point to the node that will be removed to reset it.
  • Then we will assign [ "tempNode" ] to point at [ "null" ] instead of the removed node.
  • Then we will reset the [ "tempRemovedNode" ] (old last node).
  • After that, we will decrement the value of [ "elementsCount" ] by one.
  • And finally, we will return `removedNodeValue.

Example for removing from the end of the Linked list is not empty

1# (1) 2# head 3# \ 4# \ 5# \ 6# \ 7# \ 8# \ 9# \ 10# -------------- -------------- -------------- -------------- -------------- 11# | value | next-|---->| value | next-|---->| value | next-|---->| value | next-|---->| value | next-|----> null 12# -------------- -------------- -------------- -------------- -------------- 13# Node 1 Node 2 Node 3 Node 4 Node 5 14# currently 15# (the last node) 16# (2) 17# head 18# \ 19# \ 20# \ 21# \ 22# \ 23# \ 24# \ 25# -------------- -------------- -------------- -------------- -------------- 26# | value | next-|---->| value | next-|---->| value | next-|---->| value | next-|---->| value | next-|----> null 27# -------------- -------------- -------------- -------------- -------------- ^ 28# Node 1 Node 2 Node 3 Node 4 \ Node 5 | 29# currently \ | 30# (the last node) --------------------------

Insert at a certain index of the linked list

1int insertAt(int index, int data) { 2 // Store `data` in a new object `newNode` with type of `Node` and its `newNode.next` = `null` 3 Node newNode = new Node(data); 4 5 // Check if to insert at the index of 0 6 if (index == 0) { 7 // Check if the linked list is empty 8 if (isEmpty()) { 9 // Assign `head` to point at `newNode` 10 head = newNode; 11 } else { 12 // Assign `newNode.next` to point at the old head 13 newNode.next = head; 14 // Assign `head` to point at `newNode` 15 head = newNode; 16 } 17 } else { 18 // Assign the current node which in this case we will be the attribute `head` in `tempNode` 19 Node tempNode = head; 20 21 // Keep looping until we hit the node in the position before the desired index 22 int i; 23 for (i = 0; i < index - 1; i++) { 24 // Assign the node in the position before the desired index in `tempNode` 25 tempNode = tempNode.next; 26 } 27 28 // Assign `newNode.next` to point at the `next` attribute of the node in the position before the desired index `tempNode` 29 newNode.next = tempNode.next; 30 31 // Assign the `next` attribute of the node in the position before the desired index `tempNode` to point at the `newNode` 32 tempNode.next = newNode; 33 } 34 35 // Increment the value of `elementsCount` by one 36 elementsCount++; 37} 38

In this method it will accept [ "index" ] and [ "data" ] and use it to build a new object [ "newNode" ] with type of [ "Node" ] and its [ "newNode.next" ] = [ "null" ].

  • Check if the [ "index" ] is 0
  • Check if the linked list is empty
  • Assign [ "head" ] to point at [ "newNode" ]
  • Assign [ "newNode.next" ] to point at the old head
  • Assign [ "head" ] to point at [ "newNode" ]
  • Assign the current node which in this case we will be the attribute [ "head" ] in [ "tempNode" ]
  • Keep looping until we hit the node in the position before the desired index
  • Assign the node in the position before the desired index in [ "tempNode" ]
  • Assign [ "newNode.next" ] to point at the [ "next" ] attribute of the node in the position before the desired index [ "tempNode" ]
  • Assign the [ "next" ] attribute of the node in the position before the desired index [ "tempNode" ] to point at the [ "newNode" ]
  • Increment the value of [ "elementsCount" ] by one

Example for inserting at a certain index of the Linked List is not empty

1# (1) 2# head 3# \ -------------- 4# \ | value | next-|-----------------------------------------------------------------------------> null 5# \ -------------- ^ 6# \ newNode | 7# \ | 8# \ | 9# \ | 10# -------------- -------------- -------------- -------------- -------------- | 11# | value | next-|---->| value | next-|---->| value | next-|---->| value | next-|---->| value | next-|------------------------- 12# -------------- -------------- -------------- -------------- -------------- 13# Node 1 Node 2 Node 3 Node 4 Node 5 14# (2) 15# head 16# \ -------------- 17# \ | value | next | null 18# \ ----------\-- ^ 19# \ newNode \ | 20# \ \ | 21# \ \ | 22# \ \ | 23# -------------- -------------- -------------- -------------- -------------- | 24# | value | next-|---->| value | next-|---->| value | next-|---->| value | next-|---->| value | next-|------------------------- 25# -------------- -------------- -------------- -------------- -------------- 26# Node 1 Node 2 Node 3 Node 4 Node 5 27# (3) 28# head 29# \ -------------- 30# \ | value | next | null 31# \ ----------\-- ^ 32# \ | newNode \ | 33# \ | \ | 34# \ | \ | 35# \ | \ | 36# -------------- --------|----- -------------- -------------- -------------- | 37# | value | next-|---->| value | next | | value | next-|---->| value | next-|---->| value | next-|------------------------- 38# -------------- -------------- -------------- -------------- -------------- 39# Node 1 Node 2 Node 3 Node 4 Node 5

Remove at a certain index of the linked list

1int removeAt(int index) { 2 // Check if linked list is empty 3 if (isEmpty()) { 4 // throw new Exception("LinkedList is empty!"); 5 System.err.println("LinkedList is empty!"); 6 System.exit(-1); 7 } 8 9 int removedNodeValue; 10 11 // Check if to delete at the index of 0 12 if (index == 0) { 13 if (head.next == null) { 14 // Assign `removedNodeValue` to `head.data` to return it 15 removedNodeValue = head.data; 16 // Assign `head` to point at `null` 17 head = null; 18 } else { 19 // Using `tempRemovedNode` to point at the first node to reset it 20 Node tempRemovedNode = head; 21 // Assign `removedNodeValue` to `head.data` to return it 22 removedNodeValue = head.data; 23 head = head.next; 24 25 // Reset the `tempRemovedNode` (the removed node) 26 // tempRemovedNode.next = null; 27 // tempRemovedNode.data = 0; 28 tempRemovedNode = null; 29 } 30 } else { 31 // Assign the current node which in this case we will be the attribute `head` in `tempNode` 32 Node tempNode = head; 33 // Using `tempRemovedNode` to point at the node in the position before the desired index to reset it 34 Node tempRemovedNode; 35 36 int i; 37 for (i = 0; i < index - 1; i++) { 38 tempNode = tempNode.next; 39 } 40 41 // Assign `removedNodeValue` to `head.data` to return it 42 removedNodeValue = tempNode.next.data; 43 tempRemovedNode = tempNode.next; 44 tempNode.next = tempNode.next.next; 45 46 // Reset the `tempRemovedNode` (the removed node) 47 // tempRemovedNode.next = null; 48 // tempRemovedNode.data = 0; 49 tempRemovedNode = null; 50 } 51 52 // Decrement the value of `elementsCount` by one 53 elementsCount--; 54 55 // Return `removedNodeValue 56 return removedNodeValue; 57}

In this method, it will accept [ "index" ].

  • First, we will check if the linked list is empty.
  • If true we will exist and we will print an error or we can throw an exception.
  • Check if to delete at the index of 0.
  • Assign [ "removedNodeValue" ] to [ "head.data" ] to return it.
  • Assign [ "head" ] to point at [ "null" ].
  • Use [ "tempRemovedNode" ] to point at the first node to reset it.
  • Assign [ "removedNodeValue" ] to [ "head.data" ] to return it.
  • Reset the [ "tempRemovedNode" ] (the removed node).
  • Assign the current node which in this case we will be the attribute [ "head" ] in [ "tempNode" ].
  • Use [ "tempRemovedNode" ] to point at the node in the position before the desired index to reset it.
  • Assign [ "removedNodeValue" ] to [ "head.data" ] to return it.
  • Reset the [ "tempRemovedNode" ] (the removed node).
  • Decrement the value of [ "elementsCount" ] by one.
  • Return `removedNodeValue.

Reversing a linked list

credit to Reverse a linked list (geeksforgeeks.org)

1/* Function to reverse the linked list */ 2Node reverse() { 3 // Initialize three pointers 4 // previous as NULL, 5 Node previous = null; 6 // current as head 7 Node current = head; 8 // next as NULL. 9 Node next = null; 10 11 // Iterate through the linked list. In loop, do following. 12 while (current != null) { 13 // Before changing next of current, 14 // store next node 15 // next = current->next 16 next = current.next; 17 // Now change next of current 18 // This is where actual reversing happens 19 // current->next = previous 20 current.next = previous; 21 // Move previous and current one step forward 22 // previous = current 23 // current = next 24 previous = current; 25 current = next; 26 } 27 28 head = previous; 29 return head; 30}

geeksforgeeks example for reversing a linked list

Prints the content of the linked list

1void printList() { 2 Node node = head; 3 4 while (node != null) { 5 System.out.print(node.data + " "); 6 node = node.next; 7 } 8}

Finale code

1public class Node { 2 int data; 3 Node next; 4 5 public Node(int data) { 6 this.data = data; 7 next = null; 8 } 9}
1public class MyLinkedList { 2 Node head; 3 private int elementsCount; 4 5 public MyLinkedList() { 6 head = null; 7 elementsCount = 0; 8 } 9 10 boolean isEmpty() { 11 return (elementsCount == 0); 12 } 13 14 int count() { 15 return elementsCount; 16 } 17 18 int insertFirst(int data) { 19 20 Node newNode = new Node(data); 21 22 if (isEmpty()) { 23 head = newNode; 24 } else { 25 newNode.next = head; 26 27 head = newNode; 28 } 29 30 elementsCount++; 31 return newNode.data; 32 } 33 34 int insertLast(int data) { 35 Node newNode = new Node(data); 36 37 if (isEmpty()) { 38 head = newNode; 39 } else { 40 Node tempNode = head; 41 42 while (tempNode.next != null) { 43 tempNode = tempNode.next; 44 } 45 46 tempNode.next = newNode; 47 } 48 49 elementsCount++; 50 return newNode.data; 51 } 52 53 int removeFirst() { 54 if (isEmpty()) { 55 // throw new Exception("LinkedList is empty!"); 56 System.err.println("LinkedList is empty!"); 57 System.exit(-1); 58 } 59 60 int removedNodeValue; 61 62 if (head.next == null) { 63 removedNodeValue = head.data; 64 head.next = null; 65 head.data = 0; 66 head = null; 67 } else { 68 Node tempRemovedNode = head; 69 removedNodeValue = head.data; 70 head = head.next; 71 72 // tempRemovedNode.next = null; 73 // tempRemovedNode.data = 0; 74 tempRemovedNode = null; 75 } 76 77 elementsCount--; 78 79 return removedNodeValue; 80 } 81 82 int removeLast() { 83 if (isEmpty()) { 84 // throw new Exception("LinkedList is empty!"); 85 System.err.println("LinkedList is empty!"); 86 System.exit(-1); 87 } 88 89 int removedNodeValue; 90 91 if (head.next == null) { 92 removedNodeValue = head.data; 93 head = null; 94 } else { 95 Node tempNode = head; 96 Node tempRemovedNode; 97 98 while (tempNode.next.next != null) { 99 tempNode = tempNode.next; 100 } 101 102 removedNodeValue = tempNode.next.data; 103 tempRemovedNode = tempNode.next; 104 tempNode.next = null; 105 106 // tempRemovedNode.next = null; 107 // tempNode.data = 0; 108 tempNode = null; 109 } 110 111 elementsCount--; 112 113 return removedNodeValue; 114 } 115 116 int insertAt(int index, int data) { 117 Node newNode = new Node(data); 118 119 if (index == 0) { 120 if (isEmpty()) { 121 head = newNode; 122 } else { 123 newNode.next = head; 124 head = newNode; 125 } 126 } else { 127 Node tempNode = head; 128 129 int i; 130 for (i = 0; i < index - 1; i++) { 131 tempNode = tempNode.next; 132 } 133 134 newNode.next = tempNode.next; 135 136 tempNode.next = newNode; 137 } 138 139 elementsCount++; 140 return newNode.data; 141 } 142 143 int removeAt(int index) { 144 if (isEmpty()) { 145 // throw new Exception("LinkedList is empty!"); 146 System.err.println("LinkedList is empty!"); 147 System.exit(-1); 148 } 149 150 int removedNodeValue; 151 152 if (index == 0) { 153 if (head.next == null) { 154 removedNodeValue = head.data; 155 head = null; 156 } else { 157 Node tempRemovedNode = head; 158 removedNodeValue = head.data; 159 head = head.next; 160 161 // tempRemovedNode.next = null; 162 // tempRemovedNode.data = 0; 163 tempRemovedNode = null; 164 } 165 } else { 166 Node tempNode = head; 167 Node tempRemovedNode; 168 169 int i; 170 for (i = 0; i < index - 1; i++) { 171 tempNode = tempNode.next; 172 } 173 174 removedNodeValue = tempNode.next.data; 175 tempRemovedNode = tempNode.next; 176 tempNode.next = tempNode.next.next; 177 178 // tempRemovedNode.next = null; 179 // tempRemovedNode.data = 0; 180 tempRemovedNode = null; 181 } 182 183 elementsCount--; 184 185 return removedNodeValue; 186 } 187 188 Node reverse() { 189 Node previous = null; 190 Node current = head; 191 Node next = null; 192 193 while (current != null) { 194 next = current.next; 195 current.next = previous; 196 previous = current; 197 current = next; 198 } 199 200 head = previous; 201 return head; 202 } 203 204 void printList() { 205 Node node = head; 206 207 while (node != null) { 208 System.out.print(node.data + " "); 209 node = node.next; 210 } 211 } 212}