CS133 - Data Structures and File Organizations - Flashcards

Introduction to Linked Lists

• Linked lists are our first data structure to explore.

• We will cover:

  • Singly linked lists

  • Doubly linked lists

  • Circularly linked lists

• This week we will look at linked lists:

  • Why to use linked lists?

  • How to use linked lists?

  • Different Types of linked list.

Arrays Review

• Arrays are useful structures provided by programming languages.

• However, arrays have limitations:

  • Size must be known at compilation.

  • Data is separated in memory by the same distance.

  • These limitations make inserting an item difficult.

Linked Lists as a Solution

• Linked lists overcome array limitations by linking data independently of memory location. Like a treasure hunt, each clue (data piece) points to the next location (address).

• Each data piece stores the address of the next data piece.

Simple Linked List Representation

• A basic linked list structure:

  • Data

  • Pointer (address) to the next data element.

Linked Structure Definition

• A linked structure is a collection of nodes.

  • Each node stores data.

  • Each node contains links (addresses) to other nodes.

• Nodes can be located anywhere in memory.

• Traversing the list involves using stored addresses to move between nodes, similar to following breadcrumbs.

Advantages of Linked Lists

• A data structure that makes it easy to rearrange data without having to move data in memory. Think of it like rearranging a train by switching the links between cars instead of physically moving each car.

• Example 1: Classroom of students in no order; reordering them alphabetically by seat number.

  • Solutions:

    • Change their seats (chaotic if many)

    • Leave students seated and make a list of seat numbers that corresponds to the alphabetical order of students (3,1,2)

• Example 2: Rearranging students in size order (1,3,2)

Applications of Linked Lists

• Linked lists play a critical role in dynamically managing data in companies and governments.

• Types:

  • Singly linked list: Enables movement in one direction (front to end). Like a one-way street.

  • Doubly linked list: Enables movement in both directions. Like a two-way street.

Linked Lists vs Arrays

• Programmers choose linked lists over arrays because linked lists can grow or shrink in size during runtime. Arrays are like a fixed-size bookshelf, while linked lists are like adding or removing train cars as needed.

• Adding an entry:

  • In a linked list: simply assign reference to the new entry in the last entry.

• Removing an entry:

  • In a linked list: simply remove the reference to it in the next element of the second-to-last entry.

• Arrays vs Linked list for resizing:

  • Arrays: The OS tries to increase the array by using memory alongside the array, if unavailable, then the operating system finds another location large enough to hold elements of the array and new array elements and copies old elements.

  • Linked lists: the operating system changes references to the previous item and the next item on the list, often fewer steps than resizing an array.

Structure of a Linked List Node

• Node: each entry in a linked list

  • Data: Associated with the current node.

  • Pointer to the previous node (if doubly linked).

  • Pointer to the next node.

C++ Code Example: Node Structure

typedef struct Node {
 struct Node(int data) \
 {
 this->data = data;
 previous = NULL; \
 next = NULL; \
 }
 int data;
 struct Node* previous;
 struct Node* next;
} NODE;

• The constructor initializes elements of the node when an instance of the node is created.

• structure name creates instance

Creating a Linked List of Structures

• The last member of the structure is a pointer for storing the address of another structure of the same type.

C++ Example: Linked List of Structures

#include <iostream>
#include <string>
using namespace std;

struct TeleType {
 string name;
 string phoneNo;
 TeleType *nextaddr;
};

int main() {
 TeleType tl = {"Acme, Sam", "(555) 898-2392"};
 TeleType t2 = {"Dolan, Edith", "(555) 682-3104"};
 TeleType t3 = {"Lanfrank, John", "(555) 718-4581"};

 TeleType *first;
 first = &tl; // store tl's address in first
 tl.nextaddr = &t2; // store t2's address in tl.nextaddr
 t2.nextaddr = &t3; // store t3's address in t2.nextaddr
 t3.nextaddr = NULL; // store a NULL address in t3.nextaddr

 cout << endl << first->name
 << endl << tl.nextaddr->name
 << endl << t2.nextaddr->name << endl;

 return 0;
}

Displaying Linked List Contents

void display (TeleType *contents) {
 while (contents != NULL) {
 cout << endl << setiosflags (ios::left)
 << setw(30) << contents->name
 << setw(20) << contents->phoneNo;
 contents = contents->nextaddr;
 }
 cout << endl;
 return;
}

• contents is a pointer to a structure of type TeleType

• The function displays until the end of the linked list.

Steps for Inserting a Node

1. Allocate memory for the new node.

2. Point the new node to its successor.

3. Point the new node’s predecessor to the new node.

Adding a Node to an Empty List

• Before add

  • list.head = 0

  • count = 0

• After add

  • pNew->link = list.head

  • list.head = pNew

  • count = 1

Adding a Node at the Beginning

• Before add

  • list.head = 75

  • count = 1

• After add

  • pNew->link = list.head

  • list.head = pNew

  • count = 2

Inserting in the Middle

• Before add

  • list.head = 39

  • count = 2

• After add

  • pNew->link = pPre->link

  • pPre->link = pNew

  • count = 3

Adding a Node at the End

• Before add

  • list.head = 39

  • count = 3

• After add

  • pNew->link = pPre->link

  • pPre->link = pNew

  • count = 4

Algorithm: insertNode

algorithm insertNode ( ref list  <metadata>, val pPre <node pointer> val dataIn <dataType>)
Inserts data into a new node in the linked list
Pre  list is metadata structure to a valid list
pPre is pointer to data’s logical predecessor
dataIn contains data to be inserted
Post data have been inserted in sequence
Return true if successful, false if memory overflow

1 allocate (pNew)
2 if (memory overflow)
1 return false
3 end if
5 if (pPre nulll) Adding before first node or to empty list.
1 pNew->link = list.head
2 list.head = pNew
6 else Adding in middle or at end.
1 pNew->link = pPre->link
2 pPre->link = pNew
7 end if
8 list.count = list.count + 1
9 return true
end insertNode

Inserting a Node (Code Snippet)

nodeType *newNode;
newNode = new nodeType;
newNode->data = 123;
newNode->link = current->link;
current->link = newNode;

Inserting a Node in Sorted Order (Code Snippet)

current=head;
while(current) {
 if((current->data < newnode->data) && (current->next->data > newnode->data)) {
 temp = current->next;
 current->next = newnode;
 newnode->next = temp;
 break;
 }
 current = current->next;
}

Singly Linked Lists

• The previous examples were singly linked lists.

• Contains:

  • A pointer (P) to the first element.

  • Each element stores data and a pointer to the next element.

  • The final element points towards NULL (0).

• Data can be simple types or user-defined classes.

Singly vs Doubly Linked Lists

• A node in a single linked list references the next node and not the previous node, although nothing stops you from creating a backward reference by using only the previous node reference

Singly vs. Doubly Linked List

• Singly Linked List:

  • Front pointer

• Doubly Linked List:

  • Front pointer

  • Back pointer

  • Enables traversal in both directions.

Doubly Linked List: appendNode()

void appendNode(int data) {
 NODE* n = new NODE(data);
 if(back == NULL) {
 back = n;
 front = n;
 }
 else {
 back->next = n;
 n->previous = back;
 back = n;
 }
}

Steps for Appending a Node in a Doubly Linked List

1. back->next = n;

2. n->previous = back;

3. back = n;

• Step 1: assigns the memory address of the new node to the next member of the back node

• Step 2: assigns the memory address of the back node to the previous member of the new node. This links both nodes.

• Step 3: replaces the memory address of the back node on the linked list with the memory address of the new node. This places the new node at the beginning of the linked list.

Doubly Linked List: displayNodes()

void displayNodes() {
 cout << "Nodes:";
 NODE* temp = front;
 while(temp != NULL) {
 cout << " " << temp->data;
 temp = temp->next;
 }
}

Doubly Linked List: displayNodesReverse()

void displayNodesReverse() {
 cout << "Nodes in reverse order:";
 NODE* temp = back;
 while(temp != NULL) {
 cout << " " <<  temp->data;
 temp = temp->previous;
 }
}

Deleting the First Node

• Before delete:

  • list.head = 39

  • count = 3

• After delete:

  • list.head = pLoc->link

  • count = 2

Deleting Nodes in Between

• Before delete:

  • list.head = 39

  • count = 3

• After delete:

  • pPre->link = pLoc->link

  • count = 2

Algorithm: deleteNode

algorithm deleteNode(
 ref list  <metadata>,
 val pPre <node pointer>
 val pLoc <node pointer>
 ref dataOut <dataType>)
Deletes data from a linked list and returns it calling module

Pre  list is a metadata structure to a valid list
pPre is a pointer to predecessor node
pLoc is a pointer to node to be deleted
dataOut is variable to receive deleted data

Post data have been deleted and t d t  ll

1 dataOut = pLoc->data
2 if (pPre null) Deleting first node
1 list.head = pLoc->link
3 else Deleting other nodes
1 pPre->link = pLoc->link
4 end if
5 list.count = list.count - 1
6 recycle (pLoc)
7 return
end deleteNode

Doubly Linked List: destroyList()

void destroyList() {
 NODE* temp = back;
 while(temp != NULL) {
 NODE* temp2 = temp;
 temp = temp->previous;
 delete temp2;
 }
 back = NULL;
 front = NULL;
}

• This member function removes nodes from the linked list without removing the linked list itself.

Destroying a Linked List (Step-by-Step)

• The visualization of how nodes are removed step by step

• After loop:

  • front=NULL

  • back=NULL

Deleting a Node by Value (Code Snippet)

while(current!=NULL) {
 if(current->data!=data) {
 prev=current;
 current = current->next;
 }
 else {
 prev->next = current->next;
 delete current;
 break;
 }
}

Circular Linked Lists

• The final node points back to the first node. Like a snake eating its own tail.

• Useful for tracking things continually in sequence.

Circularly Linked List

• The last node's link points to the first node

Singly Linked List Limitation

• Difficulty in tail_delete function calls.

• Scanning the entire list to find the tail element.

• Solution: Doubly Linked List.

Doubly Linked List

• Head

• Tail

• Data

Doubly Linked List Structure

• Each node has pointers to both successor and predecessor.

• Metadata:

  1. Count

  2. Position pointer for traversals

  3. Rear pointer (optional)

• Each node contains two pointers:

  1. Backward pointer – points to its predecessor

  2. Forward pointer – points to its successor

Doubly Linked List Insert

• Inserting into null list or before first node:

• Inserting between two nodes:

Doubly Linked