[\<- 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

---

[05/04 ->](05-04.md)