This is the 14th day of my participation in the First Challenge 2022

Here are some common algorithms for linear lists:

1. Build a linear linked list

Let the linear table A=(A1, A2, A3… , an), and establish A linear linked list corresponding to A.

  • Let the pointer to the first node of a linear list be list

The process of building a linear linked list is the process of dynamically generating linked nodes and linking them to the list in turn.

Algorithm idea: Algorithm:

LinkList CREAT(int n) 
{
    LinkList p, r, list = NULL;
    ElemType a;
    int i;
    for (i = 1; i <= n; i++)
    {
        READ(a); // Get a data element
        p = (LinkList)malloc(sizaof(LNode)); // Apply for a new link
        p->data = a;
        p->link = NULL; // The pointer field at the end of the list is null
        if (list= =NULL)
            list = p;
        else 
            r->link = p; // link the new node to the end of the list
        r = p; // The pointer variable r always points to the end of the list
    }
    return(list)}Copy the code

Time complexity of the algorithm: O(n)

2. Find the length of a linear list

Length of a linear list: The number of nodes contained in the list

Algorithm idea:

Specific algorithm:

int LENGTH(LinkList list)
{
    LinkList p = list;
    int n = 0;
    while(p ! =NULL) {
        n++;
        p = p->link; // the pointer p points to the next link
    }
    return n; // Return the length of the list
}
// -----------------------------------
// Recursive algorithm: A linear list is a recursive structure in which the pointer field of each linked node points to a linear list (its successor), which is the first linked node in the single linked list
int LENGTH(LinkList list)
{
    if (list! =NULL)
        return 1 + LENGTH(list->link);
    else
        return 0;
}
Copy the code

** Time complexity: **O(n)

3. Test whether the linear list is empty

int ISEMPTY(LinkList list)
{
    return list= =NULL;
    // Select * from list; // select * from list;
    return list->link == NULL;
}
Copy the code

Time complexity: O(1)

4. Determine the position of the item in the linear list

Algorithm idea:

Algorithm:

LinkList FIND(LinkList list, ElemType item)
{
    LinkList p = list;
    while(p ! =NULL&& p->data ! = item) { p = p->link; }return p;
}
Copy the code

Time complexity: O(n)

Insert a link with item before the first link in the non-empty linear table

Algorithm idea:

Algorithm:

void INSERTLINK1(LinkList &list, ElemType item)
{
    // The first address in the list
    LinkList p;
    p = (LinkList)malloc(sizeof(LNode)); // Apply for a new link
    p->data = item; // Set item to the data field of the new node
    p->link = list; // Set list to the pointer field of the new node
    list = p; // list points to the new node
}
Copy the code

Time complexity: O(1)

Insert a link with item at the end of a non-empty linear list

Algorithm idea:

Algorithm:

void INSERTLINK2(LinkList list, ElemType item)
{
    // The first address in the list
    LinkList p, r;
    r = list;
    while(r->link ! =NULL)
    {
        r = r->link; // Find the address of the end node of the list
    }
    p = (LinkList)malloc(sizeof(LNode)); // Apply for a new link
    p->data = item; // The data field of the new node is set to item
    p->link = NULL; // The pointer field of the new node is set to NULL
    r->link = p; // Insert the end of the list
}
Copy the code

Time complexity:

7. Insert item after the link indicated by pointer Q in the linear list

Algorithm idea:

Algorithm:

void INSERTLINK3(LinkList &list, LinkList q, ElemType item)
{
    // List contains the first address of the linked list. Item is the inserted element
    LinkList p;
    p = (LinkList)malloc(sizeof(LNode)); // Create a new link
    p->data = item; // The data field of the new node is set to item
    if (list= =NULL) { // When the linked list is empty
        list = p;
        p->link = NULL;
    } else { // When the list is not emptyp->link = q->link; q->link = p; }}Copy the code

Time complexity: O(1)

Insert a link with item after the ith link in the linear list

Algorithm idea:

Algorithm:

Time complexity:

9. Insert a link node with item in the linear linked list

Algorithm idea:

Algorithm:

Time complexity: