/** 获取链表中第index个节点的值。 如果索引无效,则返回-1。 */ intget(int index){ if(index < 0 || index >= size) // 索引无效 return-1; Node *p = head; // 定义指针 p 指向链表头部 int i = 0; // 从i到 index 就是 p 向后移动的步数 while(p && i < index){ p = p -> next; // 这个 next 表示,将 p 指向下一个节点,不是指针 next i++; // 向后移动一步 } if(p) return p -> val; // 返回 p 指向结构体中的值 elsereturn-1; }
/** 在链接列表的第一个元素之前添加一个值为val的节点。插入后,新节点将成为链表的第一个节点。 */ voidaddAtHead(int val){ Node *p = new Node(val); // 定义指针 p,新建了节点,值为 val, 指针为 head p -> next = head; head = p; // 把 head 置为 p 指向的内存 ++size; // 链表大小加一 }
/** 将val的节点追加到链接列表的最后一个元素。 */ voidaddAtTail(int val){ Node *p = new Node(val); // 定义一个 p 获取 head 位置 if(head == nullptr){ // 如果链表为空,直接将新节点作为头节点 head = p; return; } Node *q = head; // q 复制 head 位置 while(q -> next) // 从头开始把 q 一直向后遍历完毕 q = q -> next; q -> next = p; // 在最后添加一个新的节点,值为val ++size; }
if(index <= 0){ // 小于等于0,直接在头部插入即可 addAtHead(val); return; } Node *p = head; int i = 0; while(p && i < index - 1){ // 从头开始移动 p = p -> next; i++; } Node *q = new Node(val); // p 是索引节点的前节点,所以 p -> next 插入 q if(p){ q -> next = p -> next; // 将 p -> next 指向 q -> next p -> next = q; // 将节点 q 指向 p -> next } ++size; }
/** 如果索引有效,请删除链接列表中的第index个节点。 */ voiddeleteAtIndex(int index){ if(index < 0 || index >= size) return; // 索引无效 if(index == 0 && head != nullptr){ // index 为 0,直接删除 head 节点 Node *del = head; head = head -> next; delete del; --size; return; } Node *p = head; int i = 0; /* 要删除index,我们需要找到他的前驱节点,然后指向他的后驱即可。 */ while(p && i < index - 1){ p = p -> next; i++; } if(!p) return; // index 超过链表范围,删除失败 if(p -> next){ Node *del = p->next; // 删除节点指向 p -> next p -> next = del -> next; // 将 p -> next 指向 del -> next delete del; --size; } } };
/** 获取链表中第index个节点的值。 如果索引无效,则返回-1。 */ intget(int index){ if(index < 0 || index >= size) // 索引无效 return-1; Node *p = head; // 定义指针 p 指向链表头部 int i = 0; // 从i到 index 就是 p 向后移动的步数 while(p && i < index){ p = p -> next; // 这个 next 表示,将 p 指向下一个节点,不是指针 next i++; // 向后移动一步 } if(p) return p -> val; // 返回 p 指向结构体中的值 elsereturn-1; }
/** 在链接列表的第一个元素之前添加一个值为val的节点。插入后,新节点将成为链表的第一个节点。 */ voidaddAtHead(int val){ if(head != nullptr){ Node *node = new Node(val); node -> next = head; head -> prev = node; head = node; }else{ // 头为空,那尾肯定也是空 head = new Node(val); tail = head; } ++size; // 链表大小加一 }
/** 将val的节点追加到链接列表的最后一个元素。 */ voidaddAtTail(int val){ if(tail != nullptr){ Node *node = new Node(val); node -> prev = tail; tail -> next = node; tail = node; }else{ // 尾为空,那头肯定也是空 tail = new Node(val); head = tail; } ++size; }
Node *p = nullptr, *cur = head; int i = 0; while(cur && i < index){ // 从头开始移动 p = cur; cur = cur -> next; i++; } Node *node = new Node(val); // 创建要插入的节点 /* 特殊情况已经排除了,现在 p 和 cur 都在链表内。 */ p -> next = node; node -> prev = p; node -> next = cur; cur -> prev = node; ++size; }
/** 如果索引有效,请删除链接列表中的第index个节点。 */ voiddeleteAtIndex(int index){ if(index < 0 || index >= size) return; // 索引无效 if(!head) return; if(index == 0){ // index为头节点,删除头节点 Node *del = head; head = head -> next; if(head){ head -> prev = nullptr; }else{ tail = nullptr; } delete del; --size; return; } if(index == size - 1){ // index为尾节点,删除尾节点 Node *del = tail; tail = tail -> prev; if(tail){ tail -> next = nullptr; } delete del; --size; return; } Node *p = nullptr, *cur = head; int i = 0; /* 要删除index, */ while(cur){ if(i == index){ Node *del = cur; p -> next = cur -> next; if(cur -> next){ cur -> next ->prev = p; } delete del; --size; return; } p = cur; cur = cur -> next; ++i; } } intlength(){ return size; } };