Review On Linked Lists

Review on linked lists

Motivation ☛

A “List” is a useful structure to hold a collection of data. ■

☛

Currently, we use arrays for lists

Examples: List of ten students marks int

studentMarks[10];

List of temperatures for the last two weeks double temperature[14];

Motivation ☛

list using static array int myArray[1000]; int n;

We have to decide (to oversize) in advance the size of the array (list) ☛

list using dynamic array int* myArray; int n; cin >> n; myArray = new int[n];

We allocate an array (list) of any specified size while the program is running ☛

linked-list (dynamic size) size = ?? The list is dynamic. It can grow and shrink to any size.

Array naturally represents a (ordered) list, the link is implicit, consecutive and contiguous! Now the link is explicit, any places!

Data Link

20 0

45 1

75

array

2

Link

Data

85

45

20

85

linked list

75

Link

Data 20

45

75

85

Linked Lists: Basic Idea ☛ ☛

A linked list is an ordered collection of data Each element of the linked list has Some data ■ A link to the next element ■

☛

The link is used to chain the data Example: A linked list of integers:

Link

Data 20

45

75

85

Linked Lists: Basic Ideas ☛

The list can grow and shrink 20

45

addEnd(75), addEnd(85) 20

45

75

85

deleteEnd(85), deleteHead(20), deleteHead(45) 75

Linked Lists: Operations ☛

Original linked list of integers: 20

☛

75

85

Insertion (in the middle): 20

☛

45

old value

45

75

85

60

Deletion (in the middle) 20

45 deleted item

75

85

Definition of linked list type:

struct Node{ int data; Node* next; }; We can also: typedef Node* NodePtr;

Linked List Structure ☛

Node : Data + Link ■

Definition struct Node { int data; Node* next; };

■

Create a Node Node* p; p = new Node;

■

//contains useful information //points to next element or NULL

Delete a Node delete p;

//points to newly allocated memory

■

Access fields in a node (*p).data; //access the data field (*p).next; //access the pointer field Or it can be accessed this way p->data //access the data field p->next //access the pointer field

Representing and accessing linked lists Head

20

☛

45

75

85

We define a pointer Node* head; that points to the first node of the linked list. When the linked list is empty then head is NULL.

Passing a Linked List to a Function It is roughly the same as for an array!!! ☛

When passing a linked list to a function it should suffice to pass the value of head. Using the value of head the function can access the entire list.

☛

Problem: If a function changes the beginning of a list by inserting or deleting a node, then head will no longer point to the beginning of the list.

☛

Solution: When passing head always pass it by reference (not good!) or using a function to return a new pointer value

Implementation of an (Unsorted) Linked List

Start the first node from scratch head = NULL; Head

Node* newPtr; newPtr = new Node; newPtr->data = 20; newPtr->next = NULL; head = newPtr;

20 Head newPtr

Inserting a Node at the Beginning newPtr = new Node; newPtr->data = 13; newPtr->next = Head; head = newPtr;

20 Head

13

newPtr

Keep going … Head

50

newPtr

40

13

20

Adding an element to the head: NodePtr&

void addHead(Node*& head, int newdata){ Node* newPtr = new Node; newPtr->data = newdata; newPtr->next = Head; head = newPtr; }

Call by reference, scaring!!!

Also written (more functionally, better!) as:

Node* addHead(Node* head, int newdata){ Node* newPtr = new Node; newPtr->data = newdata; newPtr->next = Head;

return newPtr; }

Compare it with ‘addHead’ with a dynamic array implementation

Deleting the Head Node Node* p; p = head; head = head->next; delete p;

head

(to delete)

50 p

40

13

20

void deleteHead(Node*& head){ if(head != NULL){ NodePtr p = head; head = head->next; delete p; } }

As a function: Node* deleteHead(Node* head){ if(head != NULL){ NodePtr p = head; head = head->next; delete p; } return head; }

Displaying a Linked List p = head; head

20

45

p

p = p->next; head

20

45

p

A linked list is displayed by walking through its nodes one by one, and displaying their data fields (similar to an array!). void displayList(Node* head){ NodePtr p; p = head; while(p != NULL){ cout << p->data << endl; p = p->next; } }

For an array: void displayArray(int data[], int size) int n=0; while ( n<size ) { cout << data[i] << endl; n++; } }

{

Searching for a node (look at array searching first!) //return the pointer of the node that has data=item //return NULL if item does not exist Node* searchNode(Node* head, int item){ NodePtr p = head; NodePtr result = NULL; bool found=false; while((p != NULL) && (!found)){ if(p->data == item) { found = true; result = p;} p = p->next; } return result; }

Remember array searching algorithm: void main() { const int size=8; int data[size] = { 10, 7, 9, 1, 17, 30, 5, 6 }; int value; cout << "Enter search element: "; cin >> value; int n=0; int position=-1; bool found=false; while ( (n<size) && (!found) ) { if(data[n] == value) { found=true; position=n;} n++; } if(position==-1) cout << "Not found!!\n"; else cout << "Found at: " << position << endl; }

It is essentially the same!

Variations of linked lists ☛

Unsorted linked lists

☛

Sorted linked lists

Circular linked lists ☛ Doubly linked lists ☛… ☛

Further considerations for the unsorted lists: Physical copy of list for operators like ‘delection’ and ‘addHead’ ☛ ‘delete’ should be understood as a decomposition into a sub-list … ☛

Node* deleteHead(Node* head){ // physically copy head into a new one, newhead // so to keep the original list intact! Node* newhead … if(newhead != NULL){ Node* p = newhead; newhead = newhead->next; delete p; } return newhead; }

More operation: adding to the end ☛

Original linked list of integers: 50

☛

40

13

20

Add to the end (insert at the end): 50

40

13

20

60

Last element The key is how to locate the last element or node of the list!

Add to the end: void addEnd(NodePtr& head, int newdata){ NodePtr newPtr = new Node; newPtr->data = newdata; newPtr->next = NULL; NodePtr last = head; if(last != NULL){ // general non-empty list case while(last->next != NULL) last=last->next; last->next = newPtr; } else // deal with the case of empty list head = newPtr; }

Link a new object to empty list

Link new object to last->next

Add to the end as a function: NodePtr addEnd(NodePtr head, int newdata){ NodePtr newPtr = new Node; newPtr->data = newdata; newPtr->next = NULL; NodePtr last = head; if(last != NULL){ // general non-empty list case while(last->next != NULL) last=last->next; last->next = newPtr; } else // deal with the case of empty list head = newPtr; return head; }

Implementation of a Sorted Linked List

Inserting a Node 1. (a) Create a new node using: NodePtr newPtr = new node; (b) Fill in the data field correctly. 2. Find “prev” and “cur” such that the new node should be inserted between *prev and *cur. 3. Connect the new node to the list by using: (a) newPtr->next = cur; (b) prev->next = newPtr; Head

20 prev

45 33 newPtr

cur

75

...

Finding prev and cur Suppose that we want to insert or delete a node with data value newValue. Then the following code successfully finds prev and cur such that prev->data < newValue <= cur->data

It’s a kind of search algo, prev = NULL; cur = head; found=false; while( (cur!=NULL) && (!found) ) { if (newValue > cur->data) { prev=cur; cur=cur->next; } else found = true; } Prev is necessary as we can’t go back!

Finally, it is equivalent to: prev = NULL; cur = head; while( (cur!=NULL) && (newValue>cur->data) ) { prev=cur; cur=cur->next; }

Logical AND (&&) is short-circuited, sequential, i.e. if the first part is false, the second part will not be executed.

//insert item into linked list according to ascending order Node* insertNode(Node* head, int item){ NodePtr newp, cur, pre; newp = new Node; newp->data = item; pre = NULL; cur = head; while( (cur != NULL) && (item>cur->data)){ pre = cur; cur = cur->next; } if(pre == NULL){ //insert to head of linked list newp->next = head; If the position happens to be the head head = newp; } else { pre->next = newp; new->next = cur; General case } return head; }

// not recommended void type function void insertNode(NodePtr& head, int item){ NodePtr newp, cur, pre; newp = new Node; newp->data = item; pre = NULL; cur = head; while( (cur != NULL) && (item>cur->data)){ pre = cur; cur = cur->next; } if(pre == NULL){ //insert to head of linked list newp->next = head; head = newp; } else { pre->next = newp; new->next = cur; } }

Deleting a Node ☛

To delete a node from the list 1. Locate the node to be deleted (a) cur points to the node. (b) prev points to its predecessor

2. Disconnect node from list using: prev->next = cur->next;

3. Return deleted node to system: delete cur; (to delete)

Head

20

45

75

prev

cur

85

...

Delete an element in a sorted linked list: Node* deleteNode(Node* head, int item){ NodePtr prev=NULL, cur = head; while( (cur!=NULL) && (item > cur->data)){ prev = cur; cur = cur->next; } if ( cur!==NULL && cur->data==item)

Get the location

{

We can delete only if the element is present! If (cur==NULL || cur->data!=item) Item is not in the list!

if(cur==head) head = head->next; else

prev->next = cur->next;

delete cur; } return head; }

If the element is at the head General case

// in a void function, not recommended void deleteNode(NodePtr& head, int item){ NodePtr prev=NULL, cur = head; while( (cur!=NULL) && (item > cur->data)){ prev = cur; cur = cur->next; } if ( cur!==NULL && cur->data==item)

Get the location

{

We can delete only if the element is present! If (cur==NULL || cur->data!=item) Item is not in the list!

if(cur==Head) Head = Head->next; else

If the element is at the head

prev->next = cur->next;

delete cur; } }

General case