数据结构:单向链表系列1--引言

 基础知识

介绍：链表与数组一样，同属于线性表的一个子集。不同之处在于链表元素并不需要存储到一块连续的内存空间；

链表中的元素通过指针来链接并维护各个节点之间的联系，可使用连续的内存空间、亦可不使用连续的内存空间。

使用链表的原因：

1、数组类型长度是固定的，一旦申明不可以修改长度。在实际使用中我们必须事先知道元素数量的上限。

2、实际使用过程中分配的数组上限的内存空间，而事实不一定占用那么多空间。

3、插入删除成本高，必须要进行位移。插入平均位移n/2个元素，删除移动(n-1)/2个元素。最理想的时间成本

    O(1)即被删除/插入元素后面没有元素。

链表有点：

1、动态分配内存，即用即申请，占用空间大小也是动态的。

2、插入、删除方便，特别是在头和尾，修改指针地址即可。

缺点：

1、不可以随机访问，必须遍历。二分查找时间复杂度为O(n),数组二分查找时间复杂度O(log2n) （注：O(n)> O(log2n)）

2、列表中每个节点还需要额外的内存空间存储指针域（链）数据

3、数组中元素占用的存储空间是连续的，可以根据索引进行访问元素,链表不支持此操作。

数据展现：

链表第一个节点叫头节点。如果链表为空，数据域、指针域(链、引用)都是NULL

c语言中通常用结构展示数据，在java或者C#中用类和另外一个节点类(Node)来表示，LinkedList类包含Node类型的引用。

创建3个节点并遍历

c语言:

// A simple C program to introduce 
// a linked list 
#include <stdio.h>data); 
        n = n->next; 
    } 
} 

// Program to create a simple linked 
// list with 3 nodes 
int; 
  
    // Link second node with the third node 
    second->next =; 
}      

输出结果：

1 2 3      

// A simple Java program to introduce a linked list 
public class; 
        } // Constructor 
) { 
            System.out.print(n.data + " "); 
            n =); 
        Node second = new Node(2); 
        Node third = new Node(3); 
  
        /* Three nodes have been allocated dynamically. 
          We have references to these three blocks as first,   
          second and third 
  
          llist.head        second              third 
             |                |                  | 
             |                |                  | 
         +----+------+     +----+------+     +----+------+ 
         | 1  | null |     | 2  | null |     |  3 | null | 
         +----+------+     +----+------+     +----+------+ */
        
        llist.printList(); 
    } 
}      

using; 
        } // Constructor 
) { 
            Console.Write(n.data + " "); 
            n =); 
        Node second = new Node(2); 
        Node third = new Node(3); 
  
        /* Three nodes have been allocated dynamically.  
        We have references to these three blocks as first,  
        second and third  
  
        llist.head     second             third  
            |             |                 |  
            |             |                 |  
        +----+------+     +----+------+     +----+------+  
        | 1  | null |     | 2  | null |     | 3  | null |  
        +----+------+     +----+------+     +----+------+ */
        
        llist.printList(); 
    } 
}