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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
[\<- 04/27](04-27.md)
---
## A General Linear List (ADT)
- A general linear list: **a list** in which operations, such as retrievals, insertions, changes and deletions, **can be done anywhere in the list**, that is, at the beginning, int the middle, or at the end of the list
### Implementation
- Array? Yes, we can
- But we prefer Linked List
## Linked List & Array (Review)
- In an array, all the elements are kept at **consecutive memory locations** while in a linked list the elements (or nodes) may be kept at **any location** but still connected to each other
- Given the index i, how to access the element in an array/a linked list
- Array: O(1)
- Linked List: O(n)
- An array's size needs to be **known ahead of time**, or re-created when it needs to grow, while the length of a linked list can be **changed dynamically**
## Implementation
- Different data structures can be used to implement a list
- e.g. array
- We implement linear list through linked list
- **Linked List** - Linked list is a **dynamic** data structure whose length can be increased or decreased at runtime
# Basic Types of Linked List
## Singly Linked Lists
- A linked list structure in which each node has a pointer to its successor
|Head | | | | | | | | | | |
|-|----|-|----|-|----|-|----|-|----|----|
|1| -> |2| -> |3| -> |4| -> |5| -> |NULL|
- Pros
- You know the successor
- Finding the first node is O(1)
- Cons
- Don't know the predecessor
- Finding the last node is O(n)
## Circularly Linked Lists
- A linked list structure in which the last node's link points to the first node of the list
|Head | | | | | | | | | | |
|-|----|-|----|-|----|-|----|-|----|----|
|1| -> |2| -> |3| -> |4| -> |5| -> |Head|
- Pros
- You know the successor
- Finding the first node is O(1)
- Cons
- Don't know the predecessor
- Finding the last node is O(n)
## Doubly Linked Lists
- A linked list structure in which each node has a pointer to both its successor and its predecessor
|Head | | | | | | | | | | |
|-|----|-|----|-|----|-|----|-|----|----|
|1| <-> |2| <-> |3| <-> |4| <-> |5| -> |NULL|
- Pros
- You know the successor
- You know the predecessor
- Finding the first node is O(1)
- Cons
- Finding the last node is O(n)
## Doubly Linked Circular List
- A combination of doubly linked list and circularly linked list
|Head | | | | | | | | | | |
|-|----|-|----|-|----|-|----|-|----|----|
|1| <-> |2| <-> |3| <-> |4| <-> |5| <-> |Head|
- Pros
- You know the successor
- You know the predecessor
- Finding the first node is O(1)
- Finding the last node is O(1) (just look at Head-\>prev)
---
## Basic Operations
- Insertion
- Ordered list
- Random list
- Deletion
- Locate the node
- Remove it from the list
- Retrieval
- Locate a given node
- Traversal
- Go through each element in the list
- We'll mainly work on singly linked lists in this class
## Creation & Insertion
- Linked List Operations - singly linked list
- Create a list
- Insert a node
ex.
|Head | | | | | | | | |
|-|----|-|----|-|----|-|----|-|
|3| -> |10| -> |2| -> |1| -> |NULL|
- Two different structures
- NODE
- data
- pointer next
- LIST
- count
- NODE pointer head
Node Structure:
```
typedef struct node{
int data; // we use int as example
struct node *next;
} NODE;
```
List Structure:
```
typedef struct list{
int count;
struct node *head;
} LIST;
```
## Create List
- Allocate a list and initialize it
- Code:
- Check out the pseudocode (see textbook)
```
LIST *CreateList(){
LIST *plist = malloc(sizeof(LIST));
assert(plist != NULL); //failsafe
plist->count = 0;
plist->head = NULL;
return plist;
}
```
- List creation is O(1)
# Insert A Node
```
void insert(struct list *plist, struct node *pPrev, struct node *pNew){
//the code goes here
}
```
## Allocate Memory for a New Node
- Code (create a new node with data field as `val`) ?
```
NODE *pNew = malloc(sizeof(NODE));
assert(pNew != NULL); //failsafe
pNew->data = val;
pNew->next = NULL;
```
- We need to allocate memory **every time** when we generate a new node. It's the same process. So we omit it in the later discussions
|
