summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--04-27.md4
-rw-r--r--05-01.md188
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