本期主题:
数据结构之——链表
往期链接:
1.链表定义
定义:
链表由多个结点组成,结点不仅包含值,还包含到下一个结点的信息,所以通过这种方式,就将数据组合了起来,看起来就像一条链;
用C++的典型表示方式如下:
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
2.代码实现链表
实现几点:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1;
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点;
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
code:
struct node {
int val;
struct node *next;
node() {}
node(int x) :val(x), next(NULL){}
};
class MyLinkedList {
public:
struct node *cur; //当前结点
MyLinkedList() {
head = new node(NULL);
head->next = NULL;
size = 0;
}
int get(int index) {
if (index >= size)
return -1;
cur = head;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
cur = new node(val);
if (size != 0) {
//非第一个结点,将目前的head作为cur->next
cur->next = head;
}
head = cur;
size++;
}
void addAtTail(int val) {
int tmp_size = size;
cur = head;
while ((--tmp_size) && (tmp_size > 0)) { //找到最后一个结点
cur = cur->next;
}
struct node *tmp_cur = new node(val);
// if (size == 0) //无头结点情况
// {
// addAtHead(val);
// } else {
// cur->next = tmp_cur;
// }
if (size == 0)
{
head = tmp_cur;
} else {
cur->next = tmp_cur;
}
size++;
}
void addAtIndex(int index, int val) {
if (index > size)
return ;
else if (index == size)
addAtTail(val);
else if (index <= 0)
addAtHead(val);
else {
cur = head;
while ((--index) && (index > 0)) {
cur = cur->next;
}
struct node *new_node = new node(val);
new_node->next = cur->next;
cur->next = new_node;
size++;
}
}
void deleteAtIndex(int index) {
if ((index < size) && (index > 0))
{
cur = head;
while ((--index) && (index > 0)) {
cur = cur->next;
}
size--;
//非空
if (size > 0) {
cur->next = cur->next->next;
} else {
head = new node(NULL);
head->next = NULL;
size = 0;
}
} else if (index == 0) {
head = head->next;
size--;
}
else
return;
}
private:
struct node *head; //头结点
int size; //表明链表长度
};