8000 Merge pull request #13 from sdabhi23/patch-1 · Fr3oNN/Algorithms-Explanation@568af4a · GitHub
[go: up one dir, main page]
Skip to content

Commit 568af4a

Browse files
ashwekashwek
authored
Merge pull request TheAlgorithms#13 from sdabhi23/patch-1
Add explanation for doubly linked list
2 parents a875105 + 71726cb commit 568af4a

File tree

1 file changed

+112
-0
lines changed

1 file changed

+112
-0
lines changed

‎Data Structures/Linked Lists/Doubly Linked List.md

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
# Doubly Linked List
2+
3+
Singly Linked List is a linear and connected data structure made of Nodes. Each node is composed of a variable `data` where its content is stored and a pointer to the next Node on the list. The Linked List has a pointer to the first element of this Node sequence and may also have another pointer to the last Node to make operations at the far end less time-consuming. You can also store a `length` variable to store the total length.
4+
5+
A **Doubly Linked List (DLL)** contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
6+
7+
### Advantages over singly linked list
8+
- A DLL can be traversed in both forward and backward direction.
9+
- The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
10+
- We can quickly insert a new node before a given node.
11+
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.
12+
13+
### Disadvantages over singly linked list
14+
- Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though (See this and this).
15+
- All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.
16+
17+
### Time Complexity
18+
19+
| Operation | Average | Worst |
20+
|:---------:|:-------:|:-----:|
21+
| Access | Θ(n) | O(n) |
22+
| Search | Θ(n) | O(n) |
23+
| Insertion | Θ(1) | O(1) |
24+
| Deletion | Θ(1) | O(1) |
25+
26+
## Example
27+
28+
```java
29+
class LinkedList {
30+
31+
Node head; // Pointer to the first element
32+
Node tail; // Optional. Points to the last element
33+
34+
int length; // Optional
35+
36+
class Node {
37+
int data; // Node data. Can be int, string, float, templates, etc
38+
Node next; // Pointer to the next node on the list
39+
Node prev;
40+
41+
Node(int data) {
42+
this.data = data;
43+
}
44+
}
45+
46+
47+
// Adding a node at the front of the list
48+
public void push(int new_data) {
49+
50+
/* 1. allocate node
51+
* 2. put in the data */
52+
Node new_Node = new Node(new_data);
53+
54+
/* 3. Make next of new node as head and previous as NULL */
55+
new_Node.next = head;
56+
new_Node.prev = null;
57+
58+
/* 4. change prev of head node to new node */
59+
if (head != null)
60+
head.prev = new_Node;
61+
62+
/* 5. move the head to point to the new node */
63+
head = new_Node;
64+
}
65+
66+
/* Given a node as prev_node, insert a new node after the given node */
67+
public void InsertAfter(Node prev_Node, int new_data) {
68+
69+
/*1. check if the given prev_node is NULL */
70+
if (prev_Node == null) {
71+
System.out.println("The given previous node cannot be NULL ");
72+
return;
73+
}
74+
75+
/* 2. allocate node
76+
* 3. put in the data */
77+
Node new_node = new Node(new_data);
78+
79+
/* 4. Make next of new node as next of prev_node */
80+
new_node.next = prev_Node.next;
81+
82+
/* 5. Make the next of prev_node as new_node */
83+
prev_Node.next = new_node;
84+
85+
/* 6. Make prev_node as previous of new_node */
86+
new_node.prev = prev_Node;
87+
88+
/* 7. Change previous of new_node's next node */
89+
if (new_node.next != null)
90+
new_node.next.prev = new_node;
91+
}
92+
}
93+
```
94+
95+
### Adding node at front
96+
97+
![Tracing of algorithm](https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/03/DLL_add_front1.png)
98+
99+
### Add a node after a given node
100+
101+
![Tracing of algorithm](https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/03/DLL_add_middle1.png)
102+
103+
## Code Implementation Links
104+
105+
- [Java](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/DoublyLinkedList.java)
106+
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Data%20Structure/Doubly%20Linked%20List.cpp)
107+
- [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/linked_list/doubly_linked_list.py)
108+
- [Go](https://github.com/TheAlgorithms/Go/blob/master/data-structures/linked-list/double-linkedlist.go)
109+
110+
## Video Explanation
111+
112+
[A CS50 video explaining the Doubly Linked List Data Structure](https://www.youtube.com/watch?v=FHMPswJDCvU)

0 commit comments

Comments
 (0)
0