🌐 AI搜索 & 代理 主页
Skip to content

Commit 665809f

Browse files
author
Lord-of-Algorithms
committed
Add LinkedList and DoubleEndedLinkedList classes with demo
1 parent 0c2f5f2 commit 665809f

File tree

4 files changed

+378
-0
lines changed

4 files changed

+378
-0
lines changed

‎src/lineards/linkedlist/DoubleEndedLinkedList.java‎

Lines changed: 161 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,161 @@
1+
package lineards.linkedlist;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/**
6+
* Represents a singly linked list with references to both the head and tail nodes.
7+
* This structure allows efficient insertion operations at both ends of the list,
8+
* making it suitable for certain types of queue implementations. Unlike a doubly linked list,
9+
* this list only supports unidirectional traversal from the head to the tail.
10+
*/
11+
public class DoubleEndedLinkedList {
12+
13+
Node head;
14+
private Node tail;
15+
16+
/**
17+
* Checks whether the linked list is empty.
18+
*
19+
* @return true if the list contains no nodes, false otherwise.
20+
*/
21+
private boolean isEmpty() {
22+
return head == null;
23+
}
24+
25+
/**
26+
* Inserts a new node with the specified value
27+
* at the start of the list
28+
*/
29+
public void insertFirst(char value) {
30+
Node newNode = new Node(value);
31+
if (isEmpty()) {
32+
head = newNode;
33+
tail = newNode;
34+
} else {
35+
// Make the newNode point to the current head
36+
newNode.next = head;
37+
// Make the newNode as the new head
38+
head = newNode;
39+
}
40+
}
41+
42+
/**
43+
* Inserts a new node after the node with
44+
* the specified predecessor value.
45+
*
46+
* @param predValue The predecessor node's value after which the new node should be inserted.
47+
* @param value The value of the new node to be inserted.
48+
*/
49+
public void insertAfter(char predValue, char value) {
50+
Node pred = head;
51+
while (pred != null && pred.data != predValue) {
52+
pred = pred.next;
53+
}
54+
55+
if (pred != null) {
56+
Node newNode = new Node(value);
57+
newNode.next = pred.next;
58+
pred.next = newNode;
59+
if (pred == tail) {
60+
tail = newNode;
61+
}
62+
} else {
63+
throw new NoSuchElementException("Predecessor not found");
64+
}
65+
}
66+
67+
/**
68+
* Inserts a new node with the specified value
69+
* at the end of the list
70+
*/
71+
public void insertLast(char value) {
72+
Node newNode = new Node(value);
73+
if (isEmpty()) {
74+
head = newNode;
75+
tail = newNode;
76+
} else {
77+
// Update the tail's next reference
78+
// and the tail reference
79+
tail.next = newNode;
80+
tail = newNode;
81+
}
82+
}
83+
84+
/**
85+
* Deletes the first node from this list.
86+
*/
87+
public void deleteFirst() {
88+
if (isEmpty()) {
89+
throw new NoSuchElementException("The list is empty.");
90+
}
91+
92+
// If there's only one node in the list
93+
if (head == tail) {
94+
head = null;
95+
tail = null;
96+
} else {
97+
// Update the head reference to next node
98+
head = head.next;
99+
}
100+
}
101+
102+
/**
103+
* Deletes the first occurrence of a node with the specified value.
104+
*/
105+
public void deleteByValue(char value) {
106+
if (isEmpty()) {
107+
throw new NoSuchElementException("The list is empty.");
108+
}
109+
110+
if (head.data == value) {
111+
if (head == tail) {
112+
head = null;
113+
tail = null;
114+
} else {
115+
head = head.next;
116+
}
117+
return;
118+
}
119+
120+
Node pred = head;
121+
Node temp = head.next;
122+
while (temp != null && temp.data != value) {
123+
pred = pred.next;
124+
temp = temp.next;
125+
}
126+
127+
if (temp != null) {
128+
pred.next = temp.next;
129+
if (pred.next == null) {
130+
tail = pred;
131+
}
132+
} else {
133+
throw new NoSuchElementException("Value " + value + " not found in the list.");
134+
}
135+
}
136+
137+
/**
138+
* Deletes the last node from this list.
139+
*/
140+
public void deleteLast() {
141+
if (isEmpty()) {
142+
throw new NoSuchElementException("The list is empty.");
143+
}
144+
145+
// If there's only one node in the list
146+
if (head == tail) {
147+
head = null;
148+
tail = null;
149+
} else {
150+
// Find the second last node in the list
151+
Node pred = head;
152+
while (pred.next != tail) {
153+
pred = pred.next;
154+
}
155+
// Update the second last node's next
156+
// reference and the tail reference
157+
pred.next = null;
158+
tail = pred;
159+
}
160+
}
161+
}

‎src/lineards/linkedlist/LinkedList.java‎

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
package lineards.linkedlist;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/**
6+
* A singly linked list implementation for storing characters.
7+
*/
8+
public class LinkedList {
9+
10+
Node head;
11+
12+
/**
13+
* Checks whether the linked list is empty.
14+
*
15+
* @return true if the list contains no nodes, false otherwise.
16+
*/
17+
public boolean isEmpty() {
18+
return head == null;
19+
}
20+
21+
/**
22+
* Inserts the node with specified value
23+
* at the beginning of this list.
24+
*/
25+
public void insertFirst(char value) {
26+
Node node = new Node(value);
27+
node.next = head;
28+
head = node;
29+
}
30+
31+
/**
32+
* Inserts a new node after the node with
33+
* the specified predecessor value.
34+
*
35+
* @param predValue The predecessor node's value after which the new node should be inserted.
36+
* @param value The value of the new node to be inserted.
37+
*/
38+
public void insertAfter(char predValue, char value) {
39+
Node pred = head;
40+
while (pred != null && pred.data != predValue) {
41+
pred = pred.next;
42+
}
43+
if (pred != null) {
44+
Node node = new Node(value);
45+
node.next = pred.next;
46+
pred.next = node;
47+
} else {
48+
throw new NoSuchElementException("Predecessor not found");
49+
}
50+
}
51+
52+
/**
53+
* Inserts a new node with the specified value at
54+
* the end of this list.
55+
*/
56+
public void insertLast(char value) {
57+
if (isEmpty()) {
58+
head = new Node(value);
59+
return;
60+
}
61+
Node pred = head;
62+
while (pred.next != null) {
63+
pred = pred.next;
64+
}
65+
pred.next = new Node(value);
66+
}
67+
68+
/**
69+
* Deletes the first node from this list.
70+
*/
71+
public void deleteFirst() {
72+
if (isEmpty()) {
73+
throw new NoSuchElementException("The list is empty.");
74+
}
75+
head = head.next;
76+
}
77+
78+
/**
79+
* Deletes the first found node with the specified value.
80+
*/
81+
public void deleteByValue(char value) {
82+
if (isEmpty()) {
83+
throw new NoSuchElementException("The list is empty.");
84+
}
85+
if (head.data == value) {
86+
// Delete the head
87+
head = head.next;
88+
}
89+
Node pred = head;
90+
Node temp = head.next;
91+
while (temp != null && temp.data != value) {
92+
pred = pred.next;
93+
temp = temp.next;
94+
}
95+
if (temp != null) {
96+
// The node to be deleted is found.
97+
// Delete it by changing references.
98+
pred.next = temp.next;
99+
} else {
100+
throw new NoSuchElementException("Value " + value + " not found in the list.");
101+
}
102+
}
103+
104+
/**
105+
* Deletes the last node from this list.
106+
*/
107+
public void deleteLast() {
108+
if (isEmpty()) {
109+
throw new NoSuchElementException("The list is empty.");
110+
}
111+
if (head.next == null) {
112+
// There is only one node
113+
head = null;
114+
}
115+
Node pred = head;
116+
Node temp = head.next;
117+
while (temp.next != null) {
118+
pred = pred.next;
119+
temp = temp.next;
120+
}
121+
pred.next = null;
122+
}
123+
}

‎src/lineards/linkedlist/LinkedListsMain.java‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package lineards.linkedlist;
2+
3+
/**
4+
* Demonstrates the functionality of the LinkedList and DoubleEndedLinkedList classes.
5+
*/
6+
public class LinkedListsMain {
7+
public static void main(String[] args) {
8+
demoLinkedList();
9+
demoDoubleLinkedList();
10+
}
11+
12+
private static void demoLinkedList() {
13+
System.out.println("Demo LinkedList:");
14+
LinkedList linkedList = new LinkedList();
15+
linkedList.insertFirst('C');
16+
linkedList.insertFirst('B');
17+
linkedList.insertFirst('A');
18+
System.out.println("Inserting C, B, A at the start...");
19+
printList(linkedList.head);
20+
21+
linkedList.insertLast('D');
22+
System.out.println("Inserting D at the end...");
23+
printList(linkedList.head);
24+
25+
linkedList.insertAfter('B', 'E');
26+
System.out.println("Inserting E after B...");
27+
printList(linkedList.head);
28+
29+
linkedList.deleteFirst();
30+
System.out.println("Deleting the first element...");
31+
printList(linkedList.head);
32+
33+
linkedList.deleteByValue('E');
34+
System.out.println("Deleting E...");
35+
printList(linkedList.head);
36+
37+
linkedList.deleteLast();
38+
System.out.println("Deleting the last element...");
39+
printList(linkedList.head);
40+
}
41+
42+
private static void demoDoubleLinkedList() {
43+
System.out.println("\nDemo DoubleLinkedList:");
44+
DoubleEndedLinkedList doubleEndedLinkedList = new DoubleEndedLinkedList();
45+
doubleEndedLinkedList.insertFirst('1');
46+
doubleEndedLinkedList.insertFirst('2');
47+
doubleEndedLinkedList.insertFirst('3');
48+
System.out.println("Inserting 1, 2, 3 at the start...");
49+
printList(doubleEndedLinkedList.head);
50+
51+
doubleEndedLinkedList.insertLast('4');
52+
System.out.println("Inserting 4 at the end...");
53+
printList(doubleEndedLinkedList.head);
54+
55+
doubleEndedLinkedList.insertAfter('2', '5');
56+
System.out.println("Inserting 5 after 2...");
57+
printList(doubleEndedLinkedList.head);
58+
59+
doubleEndedLinkedList.deleteFirst();
60+
System.out.println("Deleting the first element...");
61+
printList(doubleEndedLinkedList.head);
62+
63+
doubleEndedLinkedList.deleteByValue('5');
64+
System.out.println("Deleting 5...");
65+
printList(doubleEndedLinkedList.head);
66+
67+
doubleEndedLinkedList.deleteLast();
68+
System.out.println("Deleting the last element...");
69+
printList(doubleEndedLinkedList.head);
70+
}
71+
72+
// Helper method to print the contents of the linked list
73+
private static void printList(Node head) {
74+
Node current = head;
75+
while (current != null) {
76+
System.out.print(current.data + " -> ");
77+
current = current.next;
78+
}
79+
System.out.println("null");
80+
}
81+
}

‎src/lineards/linkedlist/Node.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package lineards.linkedlist;
2+
3+
/**
4+
* Node in a linked list, holding a character and a reference to the next node.
5+
*/
6+
class Node {
7+
final char data;
8+
Node next;
9+
10+
Node(char data) {
11+
this.data = data;
12+
}
13+
}

0 commit comments

Comments
 (0)