1+ /*
2+ * A linked list is similar to an array, it holds values. However, links in a linked list do not have indexes.
3+ * With a linked list you do not need to predetermine it's size as it grows and shrinks as it is edited.
4+ * This is an example of a double ended, doubly linked list.
5+ * Each link references the next link and the previous one.
6+ */
7+ class LinkedList {
8+ private Link head ; //Head refers to the front of the list
9+ private Link tail ; //Tail refers to the back of the list
10+
11+ public LinkedList (){
12+ head = null ;
13+ tail = null ;
14+ }
15+
16+ public void insertHead (int x ){ //Insert an element at the head
17+ Link newLink = new Link (x ); //Create a new link with a value attached to it
18+ if (isEmpty ()) //Set the first element added to be the tail
19+ tail = newLink ;
20+ else
21+ head .previous = newLink ; // newLink <-- currenthead(head)
22+ newLink .next = head ; // newLink <--> currenthead(head)
23+ head = newLink ; // newLink(head) <--> oldhead
24+ }
25+
26+ public void insertTail (int x ){
27+ Link newLink = new Link (x );
28+ newLink .next = null ; // currentTail(tail) newlink -->
29+ tail .next = newLink ; // currentTail(tail) --> newLink -->
30+ newLink .previous = tail ; // currentTail(tail) <--> newLink -->
31+ tail = newLink ; // oldTail <--> newLink(tail) -->
32+ }
33+
34+ public Link deleteHead (){ //Delete the element at the head
35+ Link temp = head ;
36+ head = head .next ; // oldHead <--> 2ndElement(head)
37+ head .previous = null ; // oldHead --> 2ndElement(head) nothing pointing at old head so will be removed
38+ if (head == null )
39+ tail = null ;
40+ return temp ;
41+ }
42+
43+ public Link deleteTail (){
44+ Link temp = tail ;
45+ tail = tail .previous ; // 2ndLast(tail) <--> oldTail --> null
46+ tail .next = null ; // 2ndLast(tail) --> null
47+ return temp ;
48+ }
49+
50+ public Link delete (int x ){
51+ Link current = head ;
52+
53+ while (current .value != x ) //Find the position to delete
54+ current = current .next ;
55+
56+ if (current == head )
57+ deleteHead ();
58+
59+ else if (current == tail )
60+ deleteTail ();
61+
62+ else { //Before: 1 <--> 2(current) <--> 3
63+ current .previous .next = current .next ; // 1 --> 3
64+ current .next .previous = current .previous ; // 1 <--> 3
65+ }
66+ return current ;
67+ }
68+
69+ public void insertOrdered (int x ){
70+ Link newLink = new Link (x );
71+ Link current = head ;
72+ while (current != null && x > current .value ) //Find the position to insert
73+ current = current .next ;
74+
75+ if (current == head )
76+ insertHead (x );
77+
78+ else if (current == null )
79+ insertTail (x );
80+
81+ else { //Before: 1 <--> 2(current) <--> 3
82+ newLink .previous = current .previous ; // 1 <-- newLink
83+ current .previous .next = newLink ; // 1 <--> newLink
84+ newLink .next = current ; // 1 <--> newLink --> 2(current) <--> 3
85+ current .previous = newLink ; // 1 <--> newLink <--> 2(current) <--> 3
86+ }
87+ }
88+
89+ public boolean isEmpty (){ //Returns true if list is empty
90+ return (head == null );
91+ }
92+
93+ public void display (){ //Prints contents of the list
94+ Link current = head ;
95+ while (current !=null ){
96+ current .displayLink ();
97+ current = current .next ;
98+ }
99+ System .out .println ();
100+ }
101+ }
102+
103+ class Link {
104+ public int value ;
105+ public Link next ; //This points to the link in front of the new link
106+ public Link previous ; //This points to the link behind the new link
107+
108+ public Link (int value ){
109+ this .value = value ;
110+ }
111+
112+ public void displayLink (){
113+ System .out .print (value +" " );
114+ }
115+ }
116+
117+ //Example
118+ public class DoublyLinkedList {
119+ public static void main (String args []){
120+ LinkedList myList = new LinkedList ();
121+
122+ myList .insertHead (13 );
123+ myList .insertHead (7 );
124+ myList .insertHead (10 );
125+ myList .display (); // <-- 10(head) <--> 7 <--> 13(tail) -->
126+
127+ myList .insertTail (11 );
128+ myList .display (); // <-- 10(head) <--> 7 <--> 13 <--> 11(tail) -->
129+
130+ myList .deleteTail ();
131+ myList .display (); // <-- 10(head) <--> 7 <--> 13(tail) -->
132+
133+ myList .delete (7 );
134+ myList .display (); // <-- 10(head) <--> 13(tail) -->
135+
136+ myList .insertOrdered (23 );
137+ myList .insertOrdered (67 );
138+ myList .insertOrdered (3 );
139+ myList .display (); // <-- 3(head) <--> 10 <--> 13 <--> 23 <--> 67(tail) -->
140+ }
141+ }
0 commit comments