数据结构——链表（短小精悍版）

使用链表结构可以克服数组链表需要预先知道数据大小的缺点

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

单向链表：

一个单链表的节点分为两部分：数据域（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;
}