Post-class 05/01

2 files changed, 192 insertions, 0 deletions

diff --git a/04-27.md b/04-27.md
index 82d4ec8..5d06ee1 100644
--- a/04-27.md
+++ b/04-27.md
@@ -261,3 +261,7 @@ return x;
 	- Data structure - we've introduced array (possible to use others)
 
 - Please note that Queue only allows operations on its two ends. Stack only allow operations on its top end
+
+---
+
+[05/01 ->](05-01.md)
diff --git a/05-01.md b/05-01.md
new file mode 100644
index 0000000..24962a1
--- /dev/null
+++ b/05-01.md
@@ -0,0 +1,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