单链表的头插法和尾插法

头插法

• 简介
  头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点，如图所示。
  

  头插法图解.jpg

• 代码实现

//链表节点类实现
public class Node<T> {

    /**
     * 下一个节点
     */
    Node<T> next;

    /**
     * 节点存储的数据
     */
    T val;

    /**
     *
     * @param val data域
     * @param next 指针域
     */
    Node(T val,Node<T> next){
        this.val=val;
        this.next=next;
    }

    boolean hasNext(){
        return this.next!=null;
    }
}

//单链表的操作类
public class LinearList<T> {
    //链表头结点
    Node<T> head;

    public LinearList(){
        //空链表
        this.head=new Node<T>(null,null);
    }
    
    //头插法 链表 指针指向最this.head
    void add(T val){
        this.head=new Node<T>(val,this.head);
    }
    
    public static void main(String[] args) {
        LinearList<Integer> list = new LinearList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Node<Integer> head = list.head;
        while (head.hasNext()) {
            System.out.println(head.val);
            head = head.next;
        }
    }
}

尾插法

• 介绍
  头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点，如图所示。

尾插法.jpg

• C语言代码

LinkList  CreatList2(LinkList &L){
    //从表头到表尾正向建立单链表L,每次均在表尾插入元素
    int x;  // 设元素类型为整型
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s, *r=L;  //r 为表尾指针
    scanf ("%d", &x);  //输入结点的值
    while (x!=9999) {  //输入 9999 表示结束
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;  //r指向新的表尾结点
        scanf ("%d", &x);
    }
    r->next = NULL;  //尾结点指针置空
    return L;
}