Data Structure Study Notes <1> Linear List

1. Abstract Data Type Description of Linear List#

Type Name: Linear List (List)
Data Object Set: A linear list consists of an ordered sequence of n (>=0) elements (a1, a2, …, an)
Operation Set: Linear List L ∈ List, integer i represents position, element X ∈ ElementType

2. Sequential List#

1. Definition#

struct LNode {
    ElementType Data[MAXSIZE]; // Stores an array that can hold up to MAXSIZE elements
    int Last; // Index of the last element!
};
typedef struct LNode *List;

Access the element at index i: L.Data[i] or PtrL->Data[i]
Length of the linear list: L.Last + 1 or PtrL->Last + 1;

2. Operations#

The basic operations are

**1. List MakeEmpty(); // Initialize an empty linear list
2. ElementType FindKth(int K, List Ptrl); // Return the corresponding element at index K
3. int Find(ElementType X, List Ptrl); // Find the first occurrence of X in the linear list L
4. void Insert(ElementType X, int i, List Ptrl); // Insert a new element X before position i
5. void Delete(int i, List Ptrl); // Delete the element at position i
6. int Length(List Ptrl); // Return the length n of the linear list

Now let's go through them one by one.

(1) Create an Empty List#

List MakeEmpty() {
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode));
    PtrL->Last = -1;
    return PtrL;
}

(2) Find the Element at Index K#

Return the corresponding element at index K.

ElementType FindKth(int K, List Ptrl) {
    return Ptrl->Data[K];
}

(3) Find Element X#

Return the index, return -1 if not found.

int Find(ElementType X, List Ptrl) {
    int i = 0;
    while(i <= PtrL->Last && PtrL->Data[i] != X)
        i++;
    if(i > PtrL->Last) return -1; // Return -1 if not found
    else return i; // Return the storage position, i.e., index
}

(4) Insert#

Insert a new element with value X at position i (1 ≤ i ≤ n+1)

void Insert(ElementType X, int i, List Ptrl) {
    int j;
    if(Ptrl->Last == MAXSIZE-1) { // List is full, cannot insert
        printf("List is full");
        return;
    }
    if(i < 1 || i > Ptrl->Last + 2) { // Check if input is valid
        printf("Invalid position");
        return;
    }
    for(j = Ptrl->Last; j >= i-1; j--) // Note that the order cannot be from front to back here
        Ptrl->Data[j+1] = Ptrl->Data[j];
    Ptrl->Data[i-1] = X;
    Ptrl->Last++; // last still points to the last element!
    return;
}

(5) Delete#

Delete the i-th element (index i-1)

void Delete(int i, List Ptrl) {
    int j;
    if(i < 1 || i > Ptrl->Last + 1) { // Check if input is valid
        printf("The %d-th element does not exist", i);
        return;
    }
    for (j = i; j <= Ptrl->Last; j++) // Deletion must be done from front to back
        Ptrl->Data[j-1] = Ptrl->Data[j];
    Ptrl->Last--;
    return;
}

(6) Return the Length of the Linear List n#

Delete the i-th element (index i-1)

int Length(List Ptrl) {
    return Ptrl->Last + 1;
}

3. Complete Code Demonstration#

// Sequential List
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1. Definition Section
struct LNode {
    ElementType Data[MAXSIZE]; // Stores an array that can hold up to MAXSIZE elements
    int Last; // Index of the last element!
};
typedef LNode *List;
// 2. Operation Functions
// (1) Create an Empty Linear List
List MakeEmpty() {
    List Ptrl; // Create
    Ptrl = new struct LNode; // Allocate space for the first node
    Ptrl->Last = -1; // No data stored yet, set to -1
    return Ptrl; // Return the pointer
}
// (2) Find the Element at Index K
ElementType FindKth(int K, List Ptrl) {
    return Ptrl->Data[K];
}
// (3) Find Element X
int Find(ElementType X, List Ptrl) {
    int i = 0;
    while (i <= Ptrl->Last && Ptrl->Data[i] != X) {
        i++;
    }
    if (i > Ptrl->Last)
        return -1;
    else
        return i;
}
// (4) Insert Element X
void Insert(ElementType X, int i, List Ptrl) {
    if (Ptrl->Last == MAXSIZE - 1) { // List is full, cannot insert
        printf("List is full");
        return;
    }
    if (i < 1 || i > Ptrl->Last + 2) { // Check if input is valid
        printf("Invalid position");
        return;
    }
    int j;
    for (j = Ptrl->Last; j >= i - 1; j--) // Note that the order cannot be from front to back here
        Ptrl->Data[j + 1] = Ptrl->Data[j];
    Ptrl->Data[i - 1] = X;
    Ptrl->Last++; // last still points to the last element!
    return;
}
// (5) Delete
void Delete(int i, List Ptrl) {
    int j;
    if (i < 1 || i > Ptrl->Last + 1) { // Check if input is valid
        printf("The %d-th element does not exist", i);
        return;
    }
    for (j = i; j <= Ptrl->Last; j++) // Deletion must be done from front to back
        Ptrl->Data[j - 1] = Ptrl->Data[j];
    Ptrl->Last--;
    return;
}
// (6) Return the Length of the Linear List n
int Length(List Ptrl) {
    return Ptrl->Last + 1;
}
int main() {
    List P;
    P = MakeEmpty();
    for(int i = 0; i < 10; i++){
        Insert(i, i + 1, P);
    }
    cout << "The length of the sequential list is: " << Length(P) << endl;
    cout << "The 5th element is: " << FindKth(4, P) << endl;
    cout << "--Delete the 4th element--" << endl;
    Delete(4, P);
    cout << "The 5th element after deletion is: " << FindKth(4, P) << endl;
    cout << "Is there an element 3 in the list (if yes, show its index, if no, show -1): " << Find(3, P) << endl;
    cout << "Is there an element 5 in the list (if yes, show its index, if no, show -1): " << Find(5, P) << endl;
    delete [] P;
    return 0;
}

Output:

The length of the sequential list is: 10
The 5th element is: 4
--Delete the 4th element--
The 5th element after deletion is: 5
Is there an element 3 in the list (if yes, show its index, if no, show -1): -1
Is there an element 5 in the list (if yes, show its index, if no, show -1): 4

3. Chain Storage of Linear List#

Important!! A linked list does not require that two logically adjacent elements are also physically adjacent; it establishes a logical relationship between data elements through "links."
Its insertion and deletion do not require moving data elements, only modifying links.

1. Definition#

typedef struct LNode *List;
struct LNode {
    ElementType Data;
    List Next; // Pointer to the next node
} L;
List PtrL;

2. Operations#

The basic operations are

1. List Insert(ElementType X, int i, List PtrL); // Insert (insert a new node with value X after the (i-1)-th node (1<=i<=n+1))
2. List FindKth(int K, List PtrL); // Find the K-th element in the linked list by index
List Find(ElementType X, List PtrL); // Find by value: Find element K
3. List Delete(int i, List PtrL); // Delete operation (delete the node at the i-th position in the linked list)
4. int Length(List PtrL); // Calculate the length of the list

(1) Insert Operation#

Insert a new node with value X after the (i-1)-th node (1 ≤ i ≤ n+1)
(1) First construct a new node, point s to it // malloc to allocate space and assign s's Data to X
(2) Then find the (i-1)-th node in the linked list, point p to it
(3) Then modify the pointer to insert the node (insert new node s after p)
// First assign p's original next pointer to s's next pointer, then point p's next pointer to s

List Insert(ElementType X, int i, List PtrL) {
    List p, s;
    if(i == 1) { // New node inserted at the head
        s = (List)malloc(sizeof(struct LNode)); // Allocate and fill the node
        s->Data = X;
        s->Next = PtrL;
        return s; // Return new head pointer
    }
    p = Find(i - 1, PtrL); // Find the (i-1)-th node
    if(p == NULL) { // The (i-1)-th node does not exist, cannot insert
        printf("Parameter i is wrong");
        return NULL;
    } else {
        s = (List)malloc(sizeof(struct LNode)); // Allocate and fill the node
        s->Data = X;
        s->Next = p->Next; // New node is inserted after the (i-1)-th node
        p->Next = s;
        return PtrL;
    }
}

(2) Find#

If found, return a pointer to that node; if not found, return NULL

1. Find by Value: Find#

Find by value: Find element K

List Find(ElementType X, List PtrL) {
    List p = PtrL;
    while(p != NULL && p->Data != X) 
        p = p->Next;
    if(p == NULL) {          
        cout << "Element not found" << endl;
        return NULL;
    } else  return p;
}

2. Find by Index: FindKth#

Find the K-th element in the linked list by index

List FindKth(int K, List PtrL) {
    List p = PtrL;
    int i = 1;
    while (p != NULL && i < K) {
        p = p->Next;
        i++;
    }
    if(i == K) return p; // Return pointer if the K-th element is found
    else { // Otherwise return NULL
        cout << "Element not found" << endl;
        return NULL;
    }
}

(3) Delete Operation#

Delete the node at the i-th position in the linked list
(1) First find the (i-1)-th node in the linked list, point p to it; // Find(i-1, PtrL);
(2) Then point s to the node to be deleted (the next node of p) // s = p->Next;
(3) Then modify the pointer to delete the node pointed to by s // p->Next = s->Next;
(4) Finally, free the space of the node pointed to by s! // free(s)

List Delete(int i, List PtrL) {
    List p, s;
    if(i == 1) { // If the first node of the list is to be deleted
        s = PtrL; // s points to the first node
        if (PtrL != NULL) PtrL = PtrL->Next; // Delete from the linked list
        else return NULL;
        free(s); // Free the deleted node
        return PtrL;
    }
    p = FindKth(i - 1, PtrL); // Find the (i-1)-th node
    if (p == NULL) {
        printf("The %d-th node does not exist", i - 1);
        return NULL;
    } else if (p->Next == NULL) {
        printf("The %d-th node does not exist", i);
        return NULL;
    } else {
        s = p->Next; // s points to the i-th node
        p->Next = s->Next; // Delete from the linked list
        free(s); // Free the space of the deleted node
        return PtrL;
    }
}

(4) Calculate Length#

int Length(List PtrL) {
    List p = PtrL; // p points to the first node of the list
    int j = 0;
    while(p) {
        p = p->Next;
        j++;
    }
    return j;
}

3. Complete Code Demonstration#

// Linked List
#include <iostream>
using namespace std;
typedef int ElementType;
const int MAXSIZE = 1000;
// 1. Definition Section
struct LNode;
typedef LNode *List;
struct LNode {
    ElementType Data;
    List Next; // Pointer to the next node
};
List Insert(ElementType X, int i, List PtrL);  
// Insert (insert a new node with value X after the (i-1)-th node (1<=i<=n+1))
List FindKth(int K, List PtrL); // Find the K-th element in the linked list by index
List Find(ElementType X, List PtrL); // Find by value: Find element K
List Delete(int i, List PtrL); // Delete operation (delete the node at the i-th position in the linked list)
int Length(List PtrL); // Calculate the length of the list
// 2. Operation Functions
// (1) Insert Operation
List Insert(ElementType X, int i, List PtrL) {
    List p, s;
    if (i == 1) { // New node inserted at the head
        s = new struct LNode; // Allocate and fill the node
        s->Data = X;
        s->Next = PtrL;
        return s; // Return new head pointer
    }
    p = Find(i - 1, PtrL); // Find the (i-1)-th node
    if (p == NULL) { // The (i-1)-th node does not exist, cannot insert
        printf("Parameter i is wrong");
        return NULL;
    } else {
        s = new struct LNode; // Allocate and fill the node
        s->Data = X;
        s->Next = p->Next; // New node is inserted after the (i-1)-th node
        p->Next = s;
        return PtrL;
    }
}
// (2) Find
List Find(ElementType X, List PtrL) { // Find by value: Find element X
    List p = PtrL;
    while(p != NULL && p->Data != X) 
        p = p->Next;
    if(p == NULL) {          
        cout << "Element not found" << endl;
        return NULL;
    } else  return p;
}
List FindKth(int K, List PtrL) { // Find the K-th element by index
    List p = PtrL;
    int i = 1;
    while (p != NULL && i < K) {
        p = p->Next;
        i++;
    }
    if(i == K) return p; // Return pointer if the K-th element is found
    else { // Otherwise return NULL
        cout << "Element not found" << endl;
        return NULL;
    }
}
// (3) Delete
List Delete(int i, List PtrL) {
    List p, s;
    if(i == 1) { // If the first node of the list is to be deleted
        s = PtrL; // s points to the first node
        if (PtrL != NULL) PtrL = PtrL->Next; // Delete from the linked list
        else return NULL;
        delete [] s; // Free the deleted node
        return PtrL;
    }
    p = FindKth(i - 1, PtrL); // Find the (i-1)-th node
    if (p == NULL) {
        printf("The %d-th node does not exist", i - 1);
        return NULL;
    } else if (p->Next == NULL) {
        printf("The %d-th node does not exist", i);
        return NULL;
    } else {
        s = p->Next; // s points to the i-th node
        p->Next = s->Next; // Delete from the linked list
        delete [] s; // Free the space of the deleted node
        return PtrL;
    }
}
// (4) Calculate Length
int Length(List PtrL) {
    List p = PtrL; // p points to the first node of the list
    int j = 0;
    while(p) {
        p = p->Next;
        j++;
    }
    return j;
}
int main() {
    List P = NULL;
    for (int i = 0; i < 10; i++) {
        P = Insert(i, 1, P); // Head insertion method, insert element at the head
    }
    List s;
    cout << "The length of the linked list is: " << Length(P) << endl;
    cout << "The 4th element is: ";
    s = FindKth(4, P);
    if(s) cout << s->Data << endl;
    cout << "--Delete the 4th element--" << endl;
    Delete(4, P);
    cout << "The 4th element after deletion is: ";
    s = FindKth(4, P);
    if (s) cout << s->Data << endl;
    cout << "Is there an element 6 in the list: ";
    s = Find(6, P);
    if (s) cout << s->Data << endl;
    cout << "Is there an element 5 in the list: ";
    s = Find(5, P);
    if (s) cout << s->Data << endl;
    delete[] P;
    return 0;
}

Output:

The length of the linked list is: 10
The 4th element is: 6
--Delete the 4th element--
The 4th element after deletion is: 5
Is there an element 6 in the list: Element not found
Is there an element 5 in the list: 5