diff options
| -rw-r--r-- | 04-27.md | 4 | ||||
| -rw-r--r-- | 05-01.md | 188 |
2 files changed, 192 insertions, 0 deletions
@@ -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 |