directory

  • A linked list representation of a linear table
  • Single – linked list head plug and tail plug
  • The basic operation of a single linked list

A linear list of chain representation

#define ElemType int // Specify ElemType as int

typedef struct LNode {	// Define the node type of the singly linked list
	ElemType data;	/ / data domain
	struct LNode* next;	/ / pointer field
}LNode,*LinkList;
Copy the code

Two, head insert method and tail insert method

  • The first interpolation

    1. The new node inserted each time is the head of the current linked list

    2. The node order is reversed from the input order

Code implementation:

【 Lead node 】

LinkList List_HeadInsert(LinkList &L){
	LNode *s;int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	scanf("%d",&x);
	while(x! =9999) {// Input 9999 indicates the end of input
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}	
	return L;
}
Copy the code

[No leading node]

LinkList List_HeadInsert(LinkList L){
    int x;
    L=NULL;
    scanf("%d",&x);
    while(x ! =9999){
        ListLNode *s;
        s=(ListLNode*) malloc(sizeof (ListLNode));
        s->data=x;
        s->next=L;
        L=s;
        scanf("%d",&x);
    }
    return L;
}
Copy the code

  • The tail interpolation

    1. Insert a new node after the end of the table

    2. The node order is the same as the input order

【 Lead node 】

LinkList List_TailInsert(LinkList &L){
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;	// r is the end pointer of the table
	scanf("%d",&x);
	while(x! =9999) {// Input 9999 indicates the end of input
		s=(LNode)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}
Copy the code

[No leading node]

LinkList List_TailInsert(LinkList &L){
	int x;
    L=(LinkList)malloc(sizeof(ListLNode));
    scanf("%d",&x);
    L->data=x;
    L->next=NULL;
    ListLNode *s,*r=L;	// r is the end pointer of the table
    scanf("%d",&x);
    while(x! =- 1) {// Input 9999 indicates the end of input
        s=(ListLNode*)malloc(sizeof(ListLNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}
Copy the code

Basic operation of single linked list

Note: The bit order starts from 1

  • Find node values by ordinal: starting from the first node in the list, find and return the i-th node, otherwise return null for the pointer field of the last node
LNode *GetElem(LinkList &L,int i){
	int j=1;	/ / count
	LNode *p=L->next;	// p points to the first node of the single list.
	if(i==0) {// return the header if I is 0
		return L;
	}
	if(i<1) {// I value is invalid, return NULL
		return NULL;
	}
	while(p&&j<i){
		p=p->next;
		j++;
	}
	return p;
}
Copy the code
  • Find table nodes by value: Find a single linked list for a given value e, return the node if it exists, return NULL if it does not exist.
LNode *LocateElem(LinkList &L,ElemType e){
	LNode *p=L->next;	P points to the first node.
	while(p&&p->data! =e){ p=p->next; }return p;	// If not found, p already points to the NULL field of the tail
}
Copy the code
  • Insert node in bit order: Given a node value and bit order, insert the node into the corresponding bit order position of the single linked list. Returns true on success, false otherwise.
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1) {// I value is invalid, return false
		return false;
	}
	// The idea of the algorithm is to scan the list to position i-1, and then insert the list.
	LNode *p;
	int j=0;	/ / count
	p=L;
	while(p&&j<i- 1){
		p=p->next;
		j++;
	}
	if(! p){// The I value is invalid: exceeds the table length
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	// Note: The following three lines of code have order requirements.
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
} 
Copy the code
  • Specifies the forward interpolation operation of a node: After the insertion operation is too easy, the difficulty is the forward operation, and for the node specified in the first part of the linked list is the mysterious unknown region. There are now two ways to do this:1. If the linked list head pointer is given, you can choose to traverse to the previous node of the node for insertion operation. 2. If the linked list header pointer is not given, it is necessary to "sneak day", that is, to swap data domain parts after interpolation

// The following is only the code for "change the day"
bool ListPriorNode(LNode *p,ElemType e){
	if(! p){// The node given is null.
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(! s){// Failed to allocate space due to insufficient memory
		return false;
	}
	// Exchange data fields and change the pointer pointer
	s->data=p->data;
	p->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
Copy the code
  • Delete nodes in bitwise: Delete the ith node of a singly linked list, return true on success, false on failure. And returns whether to bring back the deleted data value e (subject to actual requirements).

bool ListDelete(LinkList &L,int i,ElemType &e){
	if(i<1) {return false;
	}
	int j=1;	/ / count
	LNode *p=L->next;	// Let the p pointer point to the first node of the single list
	while(p&&j<i){
		p=p->next;
		j++;
	}
	if(! p||! p->next){// I exceeds the list length or I is the last node
		return false;	
	}
	LNode *q=p->next;	// let q point to the deleted node
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
}
Copy the code
  • Delete a specified node: Returns a Boolean value, as with bitwise deletion, (brings back the deleted element). But the difficulty is different, the same algorithm has the same ideaSpecifies the forward interpolation operation of a node, but if the last node, can not be processed, can only use a lead pointer traversal to find the precursor node.
bool DeleteNode(LNode *p){
	if(! p){return false;
	}
	LNode *q=p->next;
	p->data=q->data;
	p->next=q->next;
	free(q);
	return true;
}
Copy the code