Singly-linked list
Linked list is a very important dynamic data structure. Basically, there are two types of linked list, singly-linked list and doubly-linked list. In a singly-linked list every element contains some data and a link to the next element, which allows keeping the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node. Linked list can be an underlying data structure to implement stack, queue or sorted list.Example
Sketchy, singly-linked list can be shown like this:
Operations on a singly-linked list
Concrete implementation of operations on the singly-linked list depends on the purpose, it is used for. Following the links below, you can find descriptions of the common concepts, proper for every implementation.
LinkedList :
class
SinglyLinkedListNode {
public int value;
public
SinglyLinkedListNode next;
public
SinglyLinkedListNode(int value) {
this.value = value;
next = null;
}
}
public class
SinglyLinkedList {
private
SinglyLinkedListNode head;
private
SinglyLinkedListNode tail;
public
SinglyLinkedList() {
head = null;
tail = null;
}
public void
addLast(SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
newNode.next = null;
if (head == null) {
head = newNode;
tail = newNode;
}
else {
tail.next = newNode;
tail = newNode;
}
}
}
public void
addFirst(SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
if (head == null) {
newNode.next = null;
head = newNode;
tail = newNode;
}
else {
newNode.next = head;
head = newNode;
}
}
}
public void
insertAfter(SinglyLinkedListNode previous,
SinglyLinkedListNode
newNode) {
if (newNode == null)
return;
else {
if (previous == null)
addFirst(newNode);
else if (previous == tail)
addLast(newNode);
else {
SinglyLinkedListNode
next = previous.next;
previous.next = newNode;
newNode.next = next;
}
}
}
public void removeFirst() {
if (head == null)
return;
else {
if (head == tail) {
head = null;
tail = null;
}
else {
head = head.next;
}
}
}
public void removeLast() {
if (tail == null)
return;
else {
if (head == tail) {
head = null;
tail = null;
}
else {
SinglyLinkedListNode
previousToTail = head;
while
(previousToTail.next != tail)
previousToTail
= previousToTail.next;
tail =
previousToTail;
tail.next = null;
}
}
}
public void
removeNext(SinglyLinkedListNode previous) {
if (previous == null)
removeFirst();
else if (previous.next == tail) {
tail = previous;
tail.next = null;
}
else if (previous == tail)
return;
else {
previous.next = previous.next.next;
}
}
public int traverse() {
int sum = 0;
SinglyLinkedListNode current = head;
SinglyLinkedListNode previous = null;
while (current != null) {
sum += current.value;
previous = current;
current = current.next;
}
return sum;
}
}
Java Program to reverse a Singly Linked List
I have written an efficient way to reverse a Singly Linked List using three pointers/nodes for traversal/temporary purposes. I have given a pictorial representation of what happens with near, mid and far pointer. The program is mostly self explanatory. Remember, we are using our implementation of Singly Linked List. You may visit this link if you need that class.
Note : You may click on the above image to get a clearer
picture.
Now, for the source code.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
package
dsa.linkedlist;/** *
Reverse a singly linked list *
@author Braga */public
class ReverseAList { public
static void main(String args[]){ ReverseAList
reverser = new ReverseAList(); SinglyLinkedList<Integer>
originalList = reverser.getLabRatList(10); System.out.println("Original
List : "+originalList.toString()); reverser.reverseList(originalList); System.out.println("Reversed
List : "+originalList.toString()); } public
void reverseList(SinglyLinkedList<Integer>
sourceList){ if(sourceList.size<=1){ return; } Node<Integer>
nearNode = sourceList.start; Node<Integer>
midNode, farNode; midNode
= nearNode.next; farNode
= midNode.next; nearNode.next
= null; while(farNode!=null){ midNode.next
= nearNode; nearNode
= midNode; midNode
= farNode; farNode
= farNode.next; } midNode.next
= nearNode; sourceList.start
= midNode; } private
SinglyLinkedList<Integer>
getLabRatList(int count){ SinglyLinkedList<Integer>
sampleList = new SinglyLinkedList<Integer>(); for(int
i=0;i<count;i++){ sampleList.add(i); } return
sampleList; }}//-----------------OUTPUT---------------------//Original
List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9//Reversed
List : 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 |
Loop in a Singly-Linked List
Answer: This is a very typical tech interview question that has a very elegant solution that runs in O(n) time and O(1) space. Also referred to as the “Tortoise and Hare Algorithm”, the solution uses a fast pointer (traversing the list two items at a time) and a slow pointer (traversing the list one item at a time). If there is a loop, then the fast pointer will go around the loop twice as fast as the slow pointer. At one point, these two pointers will point to the same item. Here’s some code to make this clearer.
bool hasLoop( Node *startNode )
{
Node *slowNode, *fastNode;
slowNode = fastNode = startNode;
while( slowNode && fastNode && fastNode->next )
{
if( slowNode == fastNode->next || slowNode == fastNode->next->next )
{
return true;
}
slowNode = slowNode->next;
fastNode = fastNode->next->next;
}
return false;
}Update: Thanks to RiderOfGiraffes for this solution.
The time complexity of this solution is still O(n), same as the solution provided above but this solution takes less number of steps at each point.
bool hasLoop( Node *startNode )
{
Node *tortoise, *hare;
int test_size = 2, steps_taken = 0;
tortoise = hare = startNode;
while( tortoise && hare->next )
{
hare = hare->next, steps_taken++;
if( tortoise == hare )
{
return true;
}
if ( steps_taken>=test_size )
{
steps_taken = 0, test_size *= 2;
tortoise = hare;
}
}
return false;
}
Business Intelligence Analyst
ReplyDeleteSQIAR (http://www.sqiar.com/services/bi-strategy/) is a leading Business Intelligence company.Sqiar Provide business intelligence Services Which help the company to present Information in Meaningful form.