使用链表结构可以克服数组链表需要预先知道数据大小的缺点
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单向链表：
一个单链表的节点分为两部分：数据域（data）和指针域（next）
数据域用来保存信息，指针域用来指向下一个节点的地址
单向链表查询较慢： 查找时需要从第一个节点开始一直访问到需要的位置
插入快：
删除快：删除只需要将删除结点的上一个指针指向删除节点的下一个节点。
单向链表插入的三种方法：
1.头插法：
- 将新节点的
next指针指向当前的头节点。 - 更新头节点指针为新节点。
public void insertAtHead(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;
}2.尾插法
- 如果链表为空(只有一个 head 指针并且值为null)，直接将头节点指针指向新节点。
- 链表不为空，遍历到链表的最后一个节点，将其
next指针指向新节点。
public void insertAtTail(int data) {Node newNode = new Node(data);if (head == null) {//只有一个 head 指针并且值为nullhead = newNode;return;}Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;
}
3.插入到链表的指定位置
- 遍历到插入位置的前一个节点（位置从0开始计数）。
- 将新节点的
next指针指向当前节点的next。 - 更新当前节点的
next指针为新节点。
public void insertAtPosition(int data, int position) {if (position < 0) {throw new IndexOutOfBoundsException("Position cannot be negative");}if (position == 0) {insertAtHead(data);return;}Node newNode = new Node(data);Node current = head;for (int i = 0; i < position - 1 && current != null; i++) {current = current.next;}if (current == null) {throw new IndexOutOfBoundsException("Position out of bounds");}newNode.next = current.next;current.next = newNode;
}双向链表：
双向链表的指针域有两个指针，分别指向直接后继和直接前驱。
双向链表可以从前向后遍历也可以从后向前遍历
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; //后继节点struct ListNode* prev; //前驱节点LTDataType data;}LTNode;当双向链表为空时：
双向链表头插法：
对于每个元素，创建一个新结点，并将其插入到头结点之后，使新结点成为新的头结点。
最后创建成功的双链表的顺序和输入的顺序相反，即为逆序的。
头插法的时间复杂度为O(1)。
//利用头插法创建双链表
DLinkList Init_DLinkList_head() {DLinkList head = (DLinkList) malloc(sizeof(DLinkList));head->prior = NULL;head->next = NULL;head->data = NULL;bool List_Insert (DLinkList pHead,int e){DNode* newNode = (DNode *)malloc(sizeof(DNode));newNode->data = e;newNode->next = pHead->next; //head的后继赋给新节点的后继pNode->prior = pHead; //头节点指向新节点if(pHead->next !=NULL){pHead->next->prior = newNode;}pHead->next= newNode;return true;}
}双向链表尾插法：
对于每个元素，创建一个新结点，并将其插入到头结点之后的尾部，更新尾结点的next指针和新结点的prior指针。遍历完成后，返回头结点的next指针，即为新链表的头结点。
尾插法的时间复杂度为O(n)，因为需要遍历整个双链表找到尾节点。
//利用尾插法创建双链表
DLinkList Init_DLinkList_tail() {DLinkList head = (DLinkList) malloc(sizeof(DLinkList));head->prior = NULL;head->next = NULL;head->data = NULL;void addLast(DLinkList pHead,int e){DNode* newNode = (DNode *)malloc(sizeof(DNode));newNode->data = e;}DNode* last = pHead;//遍历链表找到最后一个节点while(last->next !=NULL){last = last->next;}//让最后一个结点的后继指向新节点，新节点的后继指针置空last->next = newNode;newNode->prior = last;newNode->next = NULL;
}
