##
**What Is A Data Structure?**

A data structure is a way to store, organized/manage, and retrieve data effectively. Data structures are used in almost every program and are very important to learn and understand in software engineering.

##
**What Is A LinkedList?**

A LinkedList is a linear (O(n)) data structure that represents a sequence of elements that are the same type, which are often called Nodes. In each Node, there is the data and a pointer(s) that points to the adjacent and/or previous Node. The first Node of the list is referred to as the head, and the last Node's pointer in the list points to null or the head (Circular LinkedList). This data structure is dynamic, which means it can grow and shrink based on the number of elements inserted and deleted from the LinkedList.

In order to traverse a LinkedList, you have to start at the beginning (head) and go through each one until you've reached the desired Node. LinkedList does not allow random access.

In Java, the LinkedList implements the following interfaces, Serializable, Cloneable, Iterable, Collection, Deque, List, Queue. This is important because it gives the LinkedList data structure flexibility in its operations and usage within a program.

Below I'll demonstrate how to build a LinkedList (Singly) and some of the operations. However, the implementation will not be as specific as the implementation in the documentation, click here for the documentation.

###
*Implementation*

*Implementation*

#### Singly LinkedList

The Singly LinkedList has only one pointer for each Node that points to the memory address of the next Node. (See below)

```
/**
* @author brittcodes
*
*/
public class SinglyLinkedList {
Node head;
static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
next = null;
}
public String toString() {
return "Node [ data=" + data + ", next=" + next + " ]";
}
}
/**
* Inserts Node at the end of the list
*
* @param data, primitive data type int
*/
public void add(int data) {
//create a new node, put data in it
Node newNode = new Node(data);
//if head is null, set new node as head
if(head == null) {
head = newNode;
return;
}
//set new node next to null
newNode.next = null;
//find the node with next as null, and set that node to the new node
Node last = head;
while(last.next != null) {
last = last.next;
}
last.next = newNode;
}
/**
* Inserts a new Node after a given previous Node
*
*
* @param data, primitive data type int
*/
public void insertAfter(Node node, int data) {
//create a new node, put data in it
Node newNode = new Node(data);
//set newNode's next to node's next
newNode.next = node.next;
//set node's next to new Node
node.next = newNode;
//if list is empty, set newNode to head
if(head == null) {
newNode = head;
}
}
/**
* Inserts a new Node at beginning of list
*
*
* @param data, primitive data type int
*/
public void insertToFront(int data) {
// create a node, put data in it
Node newNode = new Node(data);
// set new node's pointer to the head
newNode.next = head;
// if list is empty, set newNode to head
if (head == null) {
newNode = head;
}
// make newNode the head
head = newNode;
}
/**
* Prints out the LinkedList
*
*/
public void printList() {
// traverse the nodes and print
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
System.out.println();
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
list.head.next = second;
second.next = third;
list.insertToFront(6);
list.printList();
list.insertAfter(third, 8);
list.printList();
list.add(23);
list.printList();
}
}
```

### Doubly LinkedList

The Doubly LinkedList has two pointers for each Node. One pointer pointing to the memory address of the previous Node, and the other pointer pointing to the memory address of the next/adjacent Node.

```
/**
* @author brittcodes
*
*/
public class DoublyLinkedList {
Node head;
static class Node {
int data;
Node next;
Node previous;
public Node(int data) {
this.data = data;
next = null;
previous = null;
}
public String toString() {
return "Node [ data=" + data + ", next=" + next + " ]";
}
}
/**
* Prints list forwards and backwards
*
* @param n, represents Node
*/
public void printList(Node n) {
Node last = null;
// Prints forward
System.out.println("\nTraverse forward");
while (n != null) {
System.out.print(n.data + " ");
last = n;
n = n.next;
}
// Prints backwards
System.out.println("\nTraverse backward");
while (last != null) {
System.out.print(last.data + " ");
last = last.previous;
}
}
/**
* Inserts Node to the beginning of list
*
* @param data, primitive data type int
*/
public void insertToFront(int data) {
// create a new Node
// put in the data
Node newNode = new Node(data);
// Make next of new node as head and previous as NULL
newNode.next = head;
newNode.previous = null;
// change previous of head node to new node
if (head != null) {
head.previous = newNode;
}
// move the head to point to the new node
head = newNode;
}
/**
* Inserts element after specified prevNode with data at the end of the list
*
* @param prevNode
* @param data
*/
public void insertAfter(Node prevNode, int data) {
if (prevNode == null) {
System.out.println("The given previous node cannot be NULL ");
return;
}
Node newNode = new Node(data);
newNode.next = prevNode.next;
prevNode.next = newNode;
newNode.previous = prevNode;
if (newNode.next != null) {
newNode.next.previous = newNode;
}
}
public void insertBefore(Node node, int data) {
Node newNode = new Node(data);
if ((head == null) && (node == null)) {
head = newNode;
}
newNode.previous = node.previous;
node.previous = newNode;
newNode.next = node;
if (newNode.previous != null) {
newNode.previous.next = newNode;
}
}
/**
* Inserts element at the end of the list
*
* @param data
*/
public void insertAtEnd(int data) {
// create a new Node
// put in the data
// make new Node next point to null
// traverse list until at last node
// make new Node previous point to last Node
// make last node next point to new Node
Node newNode = new Node(data);
Node last = head;
newNode.next = null;
if (head == null) {
head = newNode;
newNode.previous = null;
return;
}
while (last.next != null) {
last = last.next;
}
newNode.previous = last;
last.next = newNode;
}
public static void main(String[] args) {
DoublyLinkedList doubly = new DoublyLinkedList();
doubly.head = new Node(4);
Node second = new Node(5);
Node third = new Node(6);
doubly.head.next = second;
second.next = third;
third.previous = second;
second.previous = doubly.head;
doubly.printList(doubly.head);
doubly.insertAfter(doubly.head, 10);
doubly.printList(doubly.head);
doubly.insertAtEnd(25);
doubly.printList(doubly.head);
doubly.insertBefore(second, 101);
doubly.printList(doubly.head);
}
}
```

## Discussion (2)

Test

LOL