Make writing a habit together! This is the 12th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I plan to update the realization of all the code exercises of 23 Kingway data structure after class. Although the exam is generally written in pseudo-code, I still realized all of them because of obsessive-compulsive. The warehouse is here

  • The linear table
  • The list

Single linked list structure

#define ElemType int

typedef struct LNode{
  ElemType data;
  struct LNode* next;
}LNode, *LinkList; 
Copy the code

Use malloc() and free() to manage memory as much as possible:

// Create a singly linked list with no leading nodes
LinkList createList(vector<int> data) {
  if (data.size() = =0) return NULL;
  
  LNode* head = (LinkList)malloc(sizeof(LNode));
  head->data = data[0];
  head->next = NULL;
  
  LNode* p = head;
  for (int i = 1; i < data.size(a); i++) { LNode* q = (LNode*)malloc(sizeof(LNode));
    q->data = data[i];
    q->next = NULL;
    p->next = q;
    p = q;
  }
  return head;
}

// Create a singly linked list of leading nodes
LinkList createHeadList(vector<int> data) {
  if (data.size() = =0) return NULL;

  LNode* head = (LinkList)malloc(sizeof(LNode));
  head->next = NULL;

  LNode* p = head;
  for (int i = 0; i < data.size(a); i++) { LNode* q = (LNode*)malloc(sizeof(LNode));
    q->data = data[i];
    q->next = NULL;
    p->next = q;
    p = q;
  }
  return head;
}

// Print the linked list
void printList(LinkList L) {
  while(L ! =NULL) {
    cout << L->data << "";
    L = L->next;
  }
  puts("");
}
Copy the code

2.3.7, 1

  • Linked lists are inherently recursive. Each node can be regarded as a small linked list, which can be combined into a new linked list
  • Recursion is when a function calls itself directly or indirectly
  • There are only two things you need to understand to implement recursive functions: recursive relationships and recursive exits
  • In this case, the recursion is: if the current node is X, delete it; if it is not X, process the next node
  • The recursive exit is: the current node is null
  • Because the depth of recursion is O(n), so the time complexity is O(n), the space complexity is O(n).
void delX(LinkList &L, int x) {
  if (L == NULL) return;      // 1. Recursive exit
  LNode* p;
  if (L->data == x) {         // select * from (x)
    p = L;
    L = L->next;
    free(p);
    delX(L, x);
  } else {                    // the value of 3.L is not x, and the next node of L is recursively processed
    delX(L->next, x); }}Copy the code

2.3.7, 2

  • The only difference with problem 1 is that the head node, you can use the same recursion that you did in problem 1, and you don’t need to change the function at all
void delX(LinkList &L, int x) {
  if (L == NULL) return;      // 1. Recursive exit
  LNode* p;
  if (L->data == x) {         // select * from (x)
    p = L;
    L = L->next;
    free(p);
    delX(L, x);
  } else {                    // the value of 3.L is not x, and the next node of L is recursively processed
    delX(L->next, x); }}/ / call
delX(head->next, 3);
Copy the code
  • Classic two-pointer, p scans the entire list from beginning to end, and pre points to the previous node of P for easy deletion
  • Time complexity O(n), space complexity O(1)
void delX2(LinkList &L, int x) {
  LNode *pre = L, *p = L->next, *q;
  while(p ! =NULL) {
    if (p->data == x) {
      q = p;
      p = p->next;
      pre->next = p;
      free(q);
    } else{ pre = p; p = p->next; }}}Copy the code