|
1 | 1 | # Singly Linked List
|
2 | 2 |
|
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. |
4 | 4 |
|
5 |
| -A linear & connected data structure |
| 5 | +### Advantages over Arrays |
6 | 6 |
|
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 |
8 | 11 |
|
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 |
11 | 12 | - Elements can be accessed sequentially not dynamically compared to an array
|
12 | 13 | - Extra memory allocation needs to be done for pointers which connects elements in a linked list
|
13 | 14 |
|
| 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 |
14 | 25 |
|
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 |
16 | 31 |
|
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 |
21 | 38 |
|
22 |
| - class Node |
23 |
| - { |
24 |
| - int data; |
25 |
| - Node next; |
26 |
| - Node(int d) {data = d;} |
27 | 39 | }
|
28 | 40 | }
|
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 |
32 | 41 | ```
|
33 | 42 |
|
34 |
| -#### Code Implementation Links |
| 43 | +## Code Implementation Links |
35 | 44 |
|
36 | 45 | - [Java](https://github.com/TheAlgorithms/Java/blob/master/data_structures/Lists/SinglyLinkedList.java)
|
37 | 46 | - [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Linked%20List.cpp)
|
38 | 47 | - [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/LinkedList/singly_LinkedList.py)
|
39 | 48 |
|
40 |
| -#### Video Explanation |
| 49 | +## Video Explanation |
41 | 50 |
|
42 | 51 | [A CS50 video explaining the Linked List Data Structure](https://www.youtube.com/watch?v=5nsKtQuT6E8)
|
0 commit comments