数据结构与算法之双向链表(3.3)

目录

• 双向链表简介
• 双向链表重要方法讲解
• 实战检测
• 双向链表，单向链表性能对比

一 双向链表简介

双向链表.png

双向链表-只有一个元素

双向链表-一个元素.png

二 核心方法代码介绍

2.1 双向链表 node:方法

///  获取index位置对应的节点对象
- (LinkNode *)node:(NSUInteger)index {
    if ([self rangeCheck:index]) {
        return nil;
    }
    
    if (index < self.size * 0.5) {
        LinkNode *node = _first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    } else {
        LinkNode *node = _last;
        for (int i = self.size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
    }
}

2.2 双向链表 add:element方法

/// 在索引为index处插入元素值为element的节点
- (void)add:(NSUInteger)index element:(id)element {
    if (index == self.size) {   // 往最后面添加元素
        LinkNode *oldLast = _last;
        _last = [[LinkNode alloc] initWithPrev:oldLast element:element next:_first];
        if (oldLast == nil) {   // 这是链表添加的第一个元素
            _first = _last;
            _first.next = _first;
            _first.prev = _first;
        } else {    // 往一个非空链表插入新节点
            oldLast.next = _last;
            _first.prev = _last;
        }
    } else {    // 在中间插入节点
        LinkNode *next = [self node:index]; // 先获取要插入位置上的节点
        LinkNode *prev = next.prev;
        LinkNode *node = [[LinkNode alloc] initWithPrev:prev element:element next:next];
        next.prev = node;
        prev.next  = node;
        
        if (next == _first) {   // 插入到第一个位置
            _first = node;
        }
    }
    self.size++;
}

add.png

2.3 双向链表 remove:方法

// 删除索引为index的节点
- (id)remove:(NSUInteger)index {
    if ([self rangeCheck:index]) {
        return nil;
    }
    return [self removeLinkNode:[self node:index]];
}

// 删除node节点
- (id)removeLinkNode:(LinkNode *)node {
    if (self.size == 1) {
        _first = nil;
        _last = nil;
    } else {
        LinkNode *prev = node.prev;
        LinkNode *next = node.next;
        prev.next = next;
        next.prev = prev;
        
        if (node == _first) {   // idnex == 0
            _first = next;
        }
        
        if (node == _last) {    // index == size
            _last = prev;
        }
    }
    
    self.size--;
    return node.element;
}

remove.png

更多方法介绍请看文末项目链接地址

三 实战检测

LinkedList *list = [[LinkedList alloc] init];
self.list = list;
[list add:@11];
[list add:@22];
[list add:@33];
[list add:@44]; // [11, 22, 33, 44]

[list add:0 element:@55];   // [55, 11, 22, 33, 44]
[list add:2 element:@66];   // [55, 11, 66, 22, 33, 44]
[list add:list.size  element:@77];  // [55, 11, 66, 22, 33, 44, 77]

[list remove:0];    // size = 6 [11, 66, 22, 33, 44, 77]
[list remove:2];    // size = 5 [11, 66, 33, 44, 77]
[list remove:list.size - 1];    // size = 4 [11, 66, 33, 44]

NSLog(@"%lu",(unsigned long)[list indexOf:@44]);    // 3
NSLog(@"%lu",(unsigned long)[list indexOf:@22]);    // NSNotFound
NSLog(@"%lu",(unsigned long)[list contains:@33]);   // true
NSLog(@"%@",[list get:0]);  // 11
NSLog(@"%@",[list get:1]);  // 66
NSLog(@"%@",[list get:list.size - 1]);  // 4

NSLog(@"%@",list.description);

右侧注释即为打印结果

四 性能对比

4.1 双向链表 vs 单向链表

粗略对比一下删除的操作数量

• 单向链表

单向链表.png

• 双向链表

双向链表.png

操作数量缩减了近一半

4.2 双向链表 vs 动态数组

• 动态数组：开辟，销毁内存空间的次数相对少，但可能造成内存空间浪费（可以通过缩容解决）
• 双向链表：开辟，销毁内存空间的次数相对多，但不会造成内存空间的浪费

如何选择？
1.如果频繁在尾部进行添加，删除操作，动态数组，双向链表均可以选择
2.如果频繁在头部进行添加，删除操作，建议选择使用双向链表
3.如果有频繁的在任意位置进行添加，删除操作，建议选择使用双向链表
4.如果有频繁的查询操作（随机访问操作），建议选择使用动态数组

有了双向链表，单向链表是否没有任何用处了？

• 并非如此，在哈希表的设计中使用了单链表

---

本文会持续更新中，更多精彩内容敬请期待。

---

本文参考 MJ老师的 恋上数据结构与算法

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。

---

项目连接链接 - 05_DoubleLinkList