8000 Merge pull request #11 from LeoVen/master · Gekk0r/Algorithms-Explanation@9113316 · GitHub
[go: up one dir, main page]

Skip to content

Commit 9113316

Browse files
author
Christian Bender
authored
Merge pull request TheAlgorithms#11 from LeoVen/master
Update Singly Linked List.md
2 parents b70c20d + bdae7dd commit 9113316

File tree

1 file changed

+29
-20
lines changed

1 file changed

+29
-20
lines changed
Lines changed: 29 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,51 @@
11
# Singly Linked List
22

3-
#### Description
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.
44

5-
A linear & connected data structure
5+
### Advantages over Arrays
66

7-
#### How is it different from a typical array?
7+
- Size of a linked list is not fixed (dynamic size)
8+
- Deleting and adding an element is not expensive compared to an array
9+
10+
### Drawbacks
811

9-
- Size of a linked list is not fixed
10-
- Deleting and adding an element in the middle is not expensive compared to an array
1112
- Elements can be accessed sequentially not dynamically compared to an array
1213
- Extra memory allocation needs to be done for pointers which connects elements in a linked list
1314

15+
### Time Complexity
16+
17+
| Operation | Average | Worst |
18+
|:---------:|:-------:|:-----:|
19+
| Access | O(n) | O(n) |
20+
| Search | O(n) | O(n) |
21+
| Insertion | O(1) | O(1) |
22+
| Deletion | O(1) | O(1) |
23+
24+
## Example
1425

15-
#### Example
26+
```.java
27+
class LinkedList {
28+
29+
Node head; // Pointer to the first element
30+
Node tail; // Optional. Points to the last element
1631

17-
```
18-
class LinkedList
19-
{
20-
Node head;
32+
int length; // Optional
33+
34+
class Node {
35+
36+
int data; // Node data. Can be int, string, float, templates, etc
37+
Node next; // Pointer to the next node on the list
2138

22-
class Node
23-
{
24-
int data;
25-
Node next;
26-
Node(int d) {data = d;}
2739
}
2840
}
29-
30-
Here every node has a value and a pointer to the next node. The head node signifies the first element in
31-
the list
3241
```
3342

34-
#### Code Implementation Links
43+
## Code Implementation Links
3544

3645
- [Java](https://github.com/TheAlgorithms/Java/blob/master/data_structures/Lists/SinglyLinkedList.java)
3746
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Linked%20List.cpp)
3847
- [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/LinkedList/singly_LinkedList.py)
3948

40-
#### Video Explanation
49+
## Video Explanation
4150

4251
[A CS50 video explaining the Linked List Data Structure](https://www.youtube.com/watch?v=5nsKtQuT6E8)

0 commit comments

Comments
 (0)
0