单链表头插法和尾插法_单链表尾插法

 1.头插法

头插法：每次把新节点插入到头节点之后，创建的单链表和数据输入顺序相反。

 

防止单链表是空的而设的。

当链表为空的时候，带头结点的头指针就指向头结点，头结点的指针域存储的数值为NULL。

<1>.头结点

初始化一个空表，创建一个头结点，数据域不存储数据(为空)，令指针域为空。

<2>.创建第一个结点，s指针指向它；并且将这个结点放在头结点后边

 

解析：

(1).s->next = L->next;

L：表示头结点的头指针，指向头结点，存储头结点的地址。

L->next：头指针指向的头结点指针域，即L->next存储头结点指针域的地址，为NULL。

s：新建一个结点。

s->next：s结点的指针域，存储下一个结点的地址。

翻译：

s结点的指针域指向的是头结点的指针域，创建时为NULL；

(2).L->next = s;

L：表示头结点的头指针，指向头结点，存储头结点的地址。

L->next：头指针指向的头结点指针域，即L->next存储头结点指针域的地址，为NULL。

s：新建一个结点。

翻译：L->next头结点的指针域指向新节点s，保存结点s的地址。

<3>.创建第二个结点,插入到头结点后边

 

 分析同<2>.

2.尾插法

尾插法：每次把新节点链接到链表的尾部，因此需要一个尾指针永远指向链表的尾节点。

<1>.初始化后的空表，只有一个头结点，设置一个尾指针r指向头结点。 

<2>.插入一个新节点s

 

 解析：

① s->next=NULL:
s节点的指针域置空。
 
② r->next=s：
将s节点的地址赋值给r节点的指针域，即将新节点s插入尾节点r之后。
 
③ r=s：
将s节点的地址赋值给r，即r指向新的尾节点s。

 <3>.插入第二个结点

 

#include <iostream>
using namespace std;
class List{
public:
  List(){create_List();}
  ~List(){}
  void create_List();
  void insert_head(const int &d);
  void insert_end(const int &d);
  void print();
 private:
  struct Node{
  int data;
  Node *next;
  Node(const int &d) : data(d),next(NULL){ }
};
 
  Node *head;
  Node *newhead;
};
//创建单链表头节点,head->data = 0;head->next = NULl
void List::create_List(){
  head = new Node(0);
}
//头插法
void List::insert_head(const int &d){
  for(int i = 0; i < d; i++){
    Node *p = new Node(i);
    p->next = head->next;
    head->next = p;
  }
}
//尾插法
void List::insert_end(const int &d){
  Node *cur = head;
  for(int i = 0; i < d; i++){
    Node *p = new Node(i);
    cur->next = p;
    cur = p;
  }
  cur->next = NULL;
}
 
void List::print(){
  while(head->next){
    head = head->next;
    cout << head->data << " ";
  }
  cout << endl;
}
 
int main(){
  List list;
  list.insert_head(4);
  list.print();
  list.insert_end(4);
  list.print();
  return 0;
}