单链表的实现
image.png
每个链表都有一个节点next和一个value表示这个节点的值,一般我们都会有个头节点指向第一个元素，而最后一个节点next指向的是NULL
首先需要定义单链表的节点
template相当于Java中的泛型
template<class E>
struct Node {
E value;
Node<E> *next;
public:
Node(E value, Node<E> *next) {
this->value = value;
this->next = next;
}
};
常用的一些方法:添加，删除，插入等
template<class E>
class LinkedList {
// 头指针
Node<E> *head = NULL;
//数组的长度
int len = 0;
public:
/**
* 添加数据
* @param e
*/
void push(E e);
int size();
E get(int index);
void insert(int index, E e);
void remove(int index);
~LinkedList();
Node<E> *node(int i);
};
添加数据
添加数据添加到的是尾部，那么我们首先需要找到这个链表的尾部，可以从头指针开始遍历到链表的大小
template<class E>
Node<E> *LinkedList<E>::node(int index) {//O(n)的时间复杂度
Node<E> *h = head;
for (int i = 0; i < index; ++i) {
h = h->next;
}
return h;
}
添加数据就很简单了
template<class E>
void LinkedList<E>::push(E e) {
//添加一个数据
Node<E> *new_node = new Node<E>(e, NULL);
if (head) {//head是否为空
//找到尾节点
Node<E> *h = node(len - 1);
h->next = new_node;
} else {
head = new_node;
}
len++;
}
获取数据
template<class E>
E LinkedList<E>::get(int index) {
assert(index >= 0 && index < len);
return node(index)->value;
}
插入数据
此时分为两种情况，插入头部还是其他位置，插入其实就是将要插入的前一个节点，指向要插入的节点，而要插入的节点，指向之前插入的前一个节点指向的下一个节点，如下图
image.png
template<class E>
void LinkedList<E>::insert(int index, E e) {
//找到前一个
Node<E> *new_node = new Node<E>(e, NULL);
if (index == 0) {//插入在头节点
//当前头节点需要保存下
Node<E> *h = head;
head = new_node;
new_node->next = h;
} else {
//首先你必须获得了要插入的前一个节点
Node<E> *prev = node(index - 1);
//保存下prev原本指向的下一个指针的位置
Node<E> *next = prev->next;
//然后前一个指针指向新节点
prev->next = new_node;
//新节点指向之前prev原本指向的下一个指针的位置
new_node->next = next;
}
len++;
}
删除节点
image.png
删除节点就是将要删除的节点的前一个节点指向要删除的节点的i下一个节点
template<class E>
void LinkedList<E>::remove(int index) {
assert(index >= 0 && index <= len);
if (index == 0) {
Node<E> *h = head;
head = h->next;
//删除不要的节点
delete h;
} else {
Node<E> *prev = node(index - 1);
// 找到要删除的节点
Node<E> *cur = prev->next;
//获取删除节点的下个节点
Node<E> *next = cur->next;
prev->next = next;//合并就是prev->next=cur->next
//删除当前节点
delete cur;
}
len--;
}
上面我们是通过遍历去获得节点，此时的时间复杂度是O(n)级别，所以我们需要对这个时间复杂度进行优化
单链表时间复杂度优化
首先我们可以测试下我们没有优化前消耗多少时间
LinkedList<int> linkedList;
time_t start = clock();
for (int i = 0; i < 50000; ++i) {
linkedList.push(i);
}
time_t end = clock();
//没优化14s
__android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", (end - start) / CLOCKS_PER_SEC);
我电脑运行消耗的时间是14s。
优化思路：我们每次添加数据到最后一个位置的时候，如果知道最后一个位置的节点，这样就不需要遍历for循环了
LinkedList中定义尾节点
//尾节点
Node<E> *last = NULL;
修改代码后
template<class E>
void LinkedList<E>::push(E e) {
//添加一个数据
Node<E> *new_node = new Node<E>(e, NULL);
if (head) {//head是否为空
last->next = new_node;
} else {
head = new_node;
}
last=new_node;
len++;
}
此时我们时间复杂度变成了O(1)级别，再运行刚才测试时间代码，我们发现消耗时间是0
双向链表的实现
双向链表.png
双向链表结构就是有个前节点+值+后节点，当前节点的next节点指向下个节点，而下个节点的prev指向上个节点
首先定以一个双链表的节点
template<class E>
struct Node {
E value;
Node<E> *next, *prev;
public:
Node(E value, Node<E> *prev, Node<E> *next) {
this->value = value;
this->next = next;
this->prev = prev;
}
};
双链表节点的常用方法定义
template<class E>
class LinkedList {
// 头指针
Node<E> *head = NULL;
//数组的长度
int len = 0;
//尾节点
Node<E> *last = NULL;
public:
/**
* 添加数据
* @param e
*/
void push(E e);
int size();
E get(int index);
void insert(int index, E e);
E remove(int index);
~LinkedList();
Node<E> *node(int i);
void linkedLast(E e);
void linkBefore(Node<E> *node, E e);
E unlink(Node<E> *node);
};
t添加数据
添加数据首先要获取最后一个节点，让最后一个节点等于要添加的新节点
template<class E>
void LinkedList<E>::push(E e) {
linkedLast(e);
len++;
}
linkedLast代码
template<class E>
void LinkedList<E>::linkedLast(E e) {
//保存上一个最后一个节点
Node<E> *l = last;
Node<E> *new_node = new Node<E>(e, last, NULL);
//最后节点变成new_node
last = new_node;
if (head) {
l->next = new_node;
} else {
head = new_node;
}
}
二分查找的方式获得当前位置的上个节点
/**
* 遍历找到当前节点的前一个节点
*/
template<class E>
Node<E> *LinkedList<E>::node(int index) {//O(n)的时间复杂度
if (index < len >> 1) {
//从前往后遍历
Node<E> *cur = head;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur;
} else {
// 从后往前遍历
Node<E> *cur = last;
for (int i = len - 1; i > index; i--) {
cur = cur->prev;
}
return cur;
}
}
获得数据和链表的大小
template<class E>
int LinkedList<E>::size() {
return len;
}
template<class E>
E LinkedList<E>::get(int index) {
assert(index >= 0 && index < len);
return node(index)->value;
}
插入数据
image.png
首先我们要被插入数据的节点是node节点，node的前节点需要进行保存，此时，node的前节点的next指向的是node节点，而新节点的next指向的是node节点
template<class E>
void LinkedList<E>::insert(int index, E e) {
if (index == len) {
linkedLast(e);
} else {
linkBefore(node(index), e);
}
len++;
}
template<class E>
void LinkedList<E>::linkBefore(Node<E> *node, E e) {
Node<E> *prev = node->prev;
Node<E> *new_node = new Node<E>(e, prev, node);
node->prev = new_node;
if (prev) {
prev->next = new_node;
} else {
head = new_node;
}
}
移除节点
image.png
首先要被删除的节点定义名为node,我们需要获取当前node的前后两个节点，然后让node的前节点的next指向node的后节点，而node的后节点的prev指向node的前节点
template<class E>
E LinkedList<E>::remove(int index) {
assert(index >= 0 && index <= len);
return unlink(node(index));
}
template<class E>
E LinkedList<E>::unlink(Node<E> *node) {
//首先需要获得移除的左右节点
Node<E> *prev = node->prev;
Node<E> *next = node->next;
E value = node->value;
//如果prev等于空
if (prev) {
prev->next = next;
} else {
head = next;
}
if (next) {
next->prev = prev;
} else {
last = prev;
}
delete node;
len--;
return value;
}
最后需要调用析构函数释放内存
template<class E>
LinkedList<E>::~LinkedList() {
// 析构释放内存,析构所有的节点指针就可以了
Node<E> *h = head;
while (h) {
//要保存下个指针，不然当释放的时候找不到下个指针
Node<E> *next = h->next;
delete h;
h = next;
}
//头指针和尾指针要置空
head = NULL;
last = NULL;
}
