Last active
July 22, 2018 04:52
-
-
Save arttuladhar/dd77961687ada763f1d46e5c44915bc4 to your computer and use it in GitHub Desktop.
LinkedList DataStructure in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.art.datastructures; | |
import java.util.NoSuchElementException; | |
public class DoublyLinkedList<T> { | |
Node head; | |
DoublyLinkedList() { | |
this.head = null; | |
} | |
class Node { | |
private T data; | |
private Node previous; | |
private Node next; | |
public Node(T data, Node previous, Node next) { | |
this.data = data; | |
this.previous = previous; | |
this.next = next; | |
} | |
} | |
void addFirst(T data){ | |
// For First Item | |
if (head == null){ | |
head = new Node(data, null, head); | |
} else { | |
head = new Node(data, head.previous, head); | |
} | |
} | |
void addLast(T data){ | |
if (head == null) { | |
addFirst(data); | |
} else { | |
// Get Temp Pointer for Head; Traverse Nodes till End | |
Node tmp = head; | |
while (tmp.next != null) { | |
tmp = tmp.next; | |
} | |
tmp.next = new Node(data, tmp.previous, null); | |
} | |
} | |
/** | |
* Removes First Element in the List | |
*/ | |
T removeFirst() { | |
T tmp = getFirst(); | |
head = head.next; | |
return tmp; | |
} | |
private T getFirst() { | |
if (head == null) { | |
throw new NoSuchElementException(); | |
} | |
return head.data; | |
} | |
@Override | |
public String toString() { | |
StringBuilder sb = new StringBuilder(); | |
Node currentNode = head; | |
while (currentNode != null){ | |
sb.append(currentNode.data); | |
sb.append(" -- "); | |
currentNode = currentNode.next; | |
} | |
if (currentNode == null) { | |
sb.append(" [null]"); | |
} | |
return sb.toString(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.art.datastructures; | |
import com.google.common.collect.Lists; | |
import java.util.LinkedList; | |
/* | |
Example of LinkedList Implementation in JDK | |
LinkedList is a doubly-linked list implementation of the List and Deque interfaces. | |
It implements all optional list operations and permits all elements (including null). | |
Usage | |
* Add Element | |
* Remove Element | |
* Queue Operations | |
*/ | |
public class JavaLinkedListDemo { | |
public static void main(String[] args) { | |
LinkedList<String> myList = Lists.newLinkedList(); | |
myList.addLast("BLUE"); | |
System.out.println(myList); | |
myList.addLast("YELLOW"); | |
System.out.println(myList); | |
myList.addLast("PURPLE"); | |
System.out.println(myList); | |
myList.addFirst("RED"); | |
System.out.println(myList); | |
myList.removeFirst(); | |
System.out.println(myList); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.art.datastructures; | |
public class LinkedListDemo { | |
public static void main(String[] args) { | |
singlyLinkedList(); | |
doublyLinkedList(); | |
} | |
private static void singlyLinkedList(){ | |
SinglyLinkedList<String> myList = new SinglyLinkedList<>(); | |
myList.addLast("BLUE"); | |
System.out.println(myList); | |
myList.addLast("YELLOW"); | |
System.out.println(myList); | |
myList.addLast("PURPLE"); | |
System.out.println(myList); | |
myList.addFirst("RED"); | |
System.out.println(myList); | |
myList.insertAfter("RED", "PINK"); | |
System.out.println(myList); | |
myList.removeFirst(); | |
System.out.println(myList); | |
} | |
private static void doublyLinkedList(){ | |
DoublyLinkedList<String> myList = new DoublyLinkedList<>(); | |
myList.addFirst("BLUE"); | |
System.out.println(myList); | |
myList.addFirst("YELLOW"); | |
System.out.println(myList); | |
myList.addLast("PURPLE"); | |
System.out.println(myList); | |
myList.removeFirst(); | |
System.out.println(myList); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.art.datastructures; | |
import java.util.NoSuchElementException; | |
public class SinglyLinkedList<T> { | |
Node head; | |
SinglyLinkedList() { | |
this.head = null; | |
} | |
class Node { | |
private T data; | |
private Node next; | |
public Node(T data, Node next) { | |
this.data = data; | |
this.next = next; | |
} | |
} | |
/** | |
* Inserts new Node at the beginning of the List | |
*/ | |
void addFirst(T data) { | |
head = new Node(data, head); | |
} | |
/** | |
* Insert new Node at the end of the List | |
*/ | |
void addLast(T data) { | |
if (head == null) { | |
addFirst(data); | |
} else { | |
// Get Temp Pointer for Head; Traverse Nodes till End | |
Node tmp = head; | |
while (tmp.next != null) { | |
tmp = tmp.next; | |
} | |
tmp.next = new Node(data, null); | |
} | |
} | |
/** | |
* Insert new Node after the Key | |
*/ | |
void insertAfter(T key, T data) { | |
Node tmp = head; | |
while (tmp != null && !tmp.data.equals(key)) { | |
tmp = tmp.next; | |
} | |
if (tmp != null) { | |
tmp.next = new Node(data, tmp.next); | |
} | |
} | |
/** | |
* Removes First Element in the List | |
*/ | |
T removeFirst() { | |
T tmp = getFirst(); | |
head = head.next; | |
return tmp; | |
} | |
private T getFirst() { | |
if (head == null) { | |
throw new NoSuchElementException(); | |
} | |
return head.data; | |
} | |
/** | |
* Helper Override to Print LinkedList | |
*/ | |
@Override | |
public String toString() { | |
StringBuffer sb = new StringBuffer(); | |
Node currentNode = head; | |
while (currentNode != null) { | |
sb.append(currentNode.data); | |
sb.append(" -- "); | |
currentNode = currentNode.next; | |
} | |
if (currentNode == null) { | |
sb.append(" [null]"); | |
} | |
return sb.toString(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment