前言
数组与链表是最常用的数据结构中的两种,也是最简单的数据结构类型,jdk中最常用的就是ArrayList与LinkedList, 都是List的子类,LinkedList是双向链表同时也具备双向队列的功能,C++的STL库是有自带与JAVA类似的容器,自己动手写就是加深数据结构的印象,同时在使用时也能最佳的选择哪个容器
1：直接上图介绍,看ArrayList与LinkedList中的添加与删除操作
Group 6.png
从上图中可以看出ArrayList与LinkedList的主要区别
ArrayList是连续的数组,查找元素的时候非常快,LinkedList双向链表虽然有二分查找也还是只能顺着链表一个个查询,速度比较慢
ArrayList需要预开辟一定的内存空间,而LinkedList不需要
ArrayList在插入中间元素或删除中间元素(插入末尾部还是很快)时需要挪动数组中的元素,而且在数组长度不够的时候需要重新开辟数组并拷贝内存, 因此效率会比较慢, 而LinkedList相比会快速
LinkedList还实现了Dequeue双向队列功能
因此在操作随机访问较多情况的时候优先选择ArrayList,而在操作增加与删除比较多的时候选择LinkedList
2：直接上代码吧,基类List
template <class E>
class List {
protected:
int len = 0;
public:
virtual ~List();
virtual int size();
virtual bool isEmpty();
//清空
virtual void clear() = 0;
//添加
virtual bool add(const E &e) = 0;
virtual bool add(int index, const E &e) = 0;
//移除
virtual E remove(int index) = 0;
virtual E get(int index) = 0;
};
template <class E>
List<E>::~List() {
}
template <class E>
int List<E>::size() {
return len;
}
template <class E>
bool List<E>::isEmpty() {
return len <= 0;
}
3：ArrayList实现
#include <assert.h>
#include <malloc.h>
#include "List.hpp"
template <class E>
class ArrayList : public List<E> {
private:
/**
* 初始化数组大小
*/
int initialCapacity;
E *datas = NULL;
//扩充
void grow(int index, const E &e);
public:
ArrayList();
ArrayList(int initialCapacity);
~ArrayList();
void clear();
bool add(const E &e);
bool add(int index, const E &e);
E remove(int index);
E get(int index);
};
//默认大小10
template <class E>
ArrayList<E>::ArrayList() : ArrayList(10) {
}
template <class E>
ArrayList<E>::ArrayList(int initialCapacity) {
assert(initialCapacity > 1);
this->initialCapacity = initialCapacity;
this->datas = (E*) malloc(sizeof(E) * initialCapacity);
}
template <class E>
ArrayList<E>::~ArrayList() {
if (this->datas) {
free(this->datas);
this->datas = NULL;
}
}
/**
* 这里忽略扩充数组后大小超过int最大值
* @tparam E
* @param index
* @param e
*/
template <class E>
void ArrayList<E>::grow(int index, const E &e) {
initialCapacity += initialCapacity >> 1;//扩充成原先的1.5倍
E *newDatas = (E*) malloc(sizeof(E) * initialCapacity);
for (int i = 0; i < index; i++)
{
newDatas[i] = this->datas[i];
}
newDatas[index] = e;
for (int i = index + 1; i <= List<E>::len; i++)
{
newDatas[i] = datas[i - 1];
}
free(this->datas);
this->datas = newDatas;
List<E>::len++;
}
template <class E>
void ArrayList<E>::clear() {
List<E>::len = 0;
}
template <class E>
bool ArrayList<E>::add(const E &e) {
return add(ArrayList<E>::size(), e);
}
template <class E>
bool ArrayList<E>::add(int index, const E &e) {
assert(index >= 0 && index <= List<E>::len);
if (List<E>::len == initialCapacity)
{//需要扩充
grow(index, e);
return true;
}
for (int i = List<E>::len - 1; i >= index; i--) {
datas[i + 1] = datas[i];
}
datas[index] = e;
List<E>::len++;
return true;
}
template <class E>
E ArrayList<E>::remove(int index) {
assert(index >= 0 && index < List<E>::len);
E data = datas[index];
for (int i = index; i < List<E>::len - 1; i++)
{
datas[i] = datas[i + 1];
}
List<E>::len--;
return data;
}
template <class E>
E ArrayList<E>::get(int index) {
assert(index >= 0 && index < List<E>::len);
return datas[index];
}
4：LinkedList实现
#include <assert.h>
#include "List.hpp"
template <class E>
class LinkedList : public List<E> {
private:
struct Node {
E data;
Node *prev = NULL;
Node *next = NULL;
Node(const E &data, Node *prev, Node *next) : data(data) {
this->prev = prev;
this->next = next;
}
};
/**
* 头结点
*/
Node *head = NULL;
/**
* 尾结点
*/
Node *last = NULL;
/**
* 位置点节
*/
Node* node(int index);
public:
/**
* 实现父类方法
*/
~LinkedList();
void clear();
bool add(const E &e);
bool add(int index, const E &e);
E remove(int index);
E get(int index);
/**
* 新增方法
*/
void addFirst(const E &e);
void addLast(const E &e);
//移除
E removeFirst();
E removeLast();
E getFirst();
E getLast();
};
/**
* 注意此处的写法要加上typename
* @tparam E
* @param index
* @return
*/
template <class E>
typename LinkedList<E>::Node* LinkedList<E>::node(int index) {
if (index < List<E>::len >> 1)
{//小于一半的长度,从头部开始查找
Node *curr = this->head;
for (int i = 0; i < index; i++)
{
curr = curr->next;
}
return curr;
}
else {
Node *curr = this->last;
for (int i = List<E>::len - 1; i > index; i--) {
curr = curr->prev;
}
return curr;
}
}
template <class E>
LinkedList<E>::~LinkedList() {
this->clear();
}
template <class E>
void LinkedList<E>::clear() {
if (this->head)
{
Node *curr = this->head;
while (curr) {
Node *next = curr->next;
delete curr;
curr = next;
}
this->head = NULL;
this->last = NULL;
List<E>::len = 0;
}
}
template <class E>
bool LinkedList<E>::add(const E &e) {
addLast(e);
return true;
}
template <class E>
bool LinkedList<E>::add(int index, const E &e) {
assert(index >= 0 && index <= List<E>::len);
if (index == 0)
{
addFirst(e);
return true;
}
if (index == List<E>::len)
{
addLast(e);
return true;
}
Node *addPreNode = node(index - 1);
Node *addNextNode = addPreNode->next;
Node *new_node = new Node(e, addPreNode, addNextNode);
addPreNode->next = new_node;
addNextNode->prev = new_node;
List<E>::len++;
return true;
}
template <class E>
E LinkedList<E>::remove(int index) {
assert(index >= 0 && index < List<E>::len);
if (index == 0)
{
return removeFirst();
}
if (index == List<E>::len - 1)
{
return removeLast();
}
Node *removeNode = node(index);
Node *removePreNode = removeNode->prev;
Node *removeNextNode = removeNode->next;
removePreNode->next = removeNextNode;
removeNextNode->prev = removePreNode;
E e = removeNode->data;
delete removeNode;
List<E>::len--;
return e;
}
template <class E>
E LinkedList<E>::get(int index) {
assert(index >= 0 && index < List<E>::len);
Node *getNode = node(index);
return getNode->data;
}
template <class E>
void LinkedList<E>::addFirst(const E &e) {
Node *newNode = new Node(e, NULL, head);
if (this->head)
{
this->head->prev = newNode;
this->head = newNode;
}
else {
this->last = newNode;
this->head = newNode;
}
List<E>::len++;
}
template <class E>
void LinkedList<E>::addLast(const E &e) {
Node *newNode = new Node(e, last, NULL);
if (this->head)
{
this->last->next = newNode;
this->last = newNode;
}
else {
this->last = newNode;
this->head = newNode;
}
List<E>::len++;
}
template <class E>
E LinkedList<E>::removeFirst() {
assert(this->head);
Node *removeNode = this->head;
Node *headNextNode = removeNode->next;
if (headNextNode)
{//有多个结点
headNextNode->prev = NULL;
this->head = headNextNode;
}
else {//只有一个结点
this->head = NULL;
this->last = NULL;
}
E e = removeNode->data;
delete removeNode;
List<E>::len--;
return e;
}
template <class E>
E LinkedList<E>::removeLast() {
assert(this->last);
Node *removeNode = this->last;
Node *lastPreNode = removeNode->prev;
if (lastPreNode)
{//有多个结点
lastPreNode->next = NULL;
this->last = lastPreNode;
}
else {//只有一个结点
this->head = NULL;
this->last = NULL;
}
E e = removeNode->data;
delete removeNode;
List<E>::len--;
return e;
}
template <class E>
E LinkedList<E>::getFirst() {
assert(List<E>::len > 0);
return this->head->data;
}
template <class E>
E LinkedList<E>::getLast() {
assert(List<E>::len > 0);
return this->last->data;
}
5：最后测试
JNIEXPORT void JNICALL
Java_you_chen_ctest_MainActivity_test0(JNIEnv *env, jobject /* this */) {
List<Dog*> *list = new ArrayList<Dog*>();
Dog *dog1 = new Dog("dog1*", 11);
Dog *dog2 = new Dog("dog2*", 22);
Dog *dog3 = new Dog("dog3*", 33);
list->add(dog1);
list->add(dog3);
list->add(1, dog2);
list->remove(2);
for (int i = 0; i < list->size(); ++i) {
Dog *dog = list->get(i);
LOGD("Dog %s, %d", dog->name, dog->age);
}
delete list; delete dog1; delete dog2; delete dog3;
LOGD("------divider--------- \n\n\n");
ArrayList<Dog> dogs1;
dogs1.add(Dog{"dog1", 13 });
dogs1.add(Dog{"dog2", 25 });
Dog d1 = {"dog3", 38};
dogs1.add(d1);
dogs1.remove(1);
for (int i = 0; i < dogs1.size(); ++i) {
Dog dog = dogs1.get(i);
LOGD("Dog %s, %d", dog.name, dog.age);
}
dogs1.clear();
}
网友评论