Single step analysis of double linked list insertion and deletion (14)

1. Double linked list definition

Single linked list can only operate backward , Cannot move forward . Double linked list can operate forward and backward .

Double linked list features ： The following figure explains

A precursor pointer ：ai The forerunner of , Point to ai-1 node , Storage ai-1 The address of .

Data fields ： Storing data

A rear drive pointer ：ai Rear drive pointer , Point to ai+1 node , Storage ai+1 The address of .

The above concepts are the key to understanding the two-way linked list .

2. The insert

In the i In front of a node , Insert a e node .

analysis ：

<1>.p->prior->next = s;

p： To point to ai A pointer to a node

p->prior： Means to store ai-1 The address of the node .

p->prior->next： Means to store ai-1 The trailing pointer of the address of the node , Not inserted e Before node , It's pointing ai Nodal , But now let it point to e The address of the node ( The pointer s).

translate ： take ai-1 The node's back drive pointer points to s, Save s The address of the node .

<2>.s->prior = p->prior;

s： Point to the... To insert e A pointer to a node , namely e The address of the node .

s->prior：e node address s The forerunner of , Store the address of the previous node .

p： To point to ai A pointer to a node , namely ai The address of the node .

p->prior： Means to store ai-1 The address of the node .

translate ：s The precursor pointer of the node points to ai-1 The address of .

<3>.s->next = p;

s： Point to the... To insert e A pointer to a node , namely e The address of the node .

s->next：s The trailing pointer of the node ;

p： To point to ai A pointer to a node , namely ai The address of the node .

translate ：s The trailing pointer of the node points to p node , namely s The back drive pointer of the node is saved ai The address of the node .

<4>.p->prior = s;

p： To point to ai A pointer to a node , namely ai The address of the node .

p->prior： Means to store ai-1 The address of the node .

s： Point to the... To insert e A pointer to a node , namely e The address of the node .

translate ： Point to ai Nodal p The precursor of the pointer points to e node , namely ai The node precursor pointer is saved s The address of the node .

thus , take e The node is inserted in ai-1 and ai Between nodes .

3. Delete operation

Delete ai node .

  analysis ：

<1>.p->prior->next = p->next;

p： Point to ai A pointer to a node .

p->prior：ai The precursor pointer of the node , Save the ai-1 The address of the node .

p->prior->next：ai-1 The subsequent pointer field of the node , Actually store ai The address of the node .

p->next：ai The subsequent pointer of the node , Stored ai+1 The address of the node .

translate ： take ai-1 The subsequent pointer of the node points to ai The subsequent pointer of the node , because ai The subsequent pointers of the store ai+1 The address of , In fact, that is ai-1 The back pointer of the node points to ai+1 The address of the node , Save ai+1 The address of the node , Skip the ai node .

<2>.p->next->prior = p->prior;

p： Point to ai A pointer to a node .

p->next：ai The subsequent pointer of the node , preserved ai+1 The address of the node .

p->next->prior：ai+1 The precursor pointer of the node , preserved ai The address of the node .

p->prior：ai The precursor pointer of the node , Save the ai-1 The address of the node .

translate ： take ai+1 The precursor pointer of the node , Point to ai-1 The address of the node .

thus , Is deleted ai node .