数据结构系列: Objective-C 实现双链表

接续上一篇《数据结构系列: Objective-C 实现单链表》

双向链表

摘自《双向链表 - 维基百科, 自由的百科全书》

双向链表, 又称为双链表, 是链表 https://zh.wikipedia.org/wiki/链表的一种, 它的每个数据结点中都有两个指针, 分别指向直接后继和直接前驱. 所以, 从双向链表中的任意一个结点开始, 都可以很方便地访问它的前驱结点和后继结点.

摘自《链表 - 维基百科, 自由的百科全书》

一种更复杂的链表是 "双向链表" 或 "双面链表". 每个节点有两个连接: 一个指向前一个节点,(当此 "连接" 为第一个 "连接" 时, 指向空值或者空列表); 而另一个指向下一个节点,(当此 "连接" 为最后一个 "连接" 时, 指向空值或者空列表)

在一些低级语言中, XOR-linking https://zh.wikipedia.org/wiki/XOR_linked_list 提供一种在双向链表中通过用一个词来表示两个链接(前后), 我们通常不提倡这种做法.

双向链表也叫双链表. 双向链表中不仅有指向后一个节点的指针, 还有指向前一个节点的指针. 这样可以从任何一个节点访问前一个节点, 当然也可以访问后一个节点, 以至整个链表. 一般是在需要大批量的另外储存数据在链表中的位置的时候用. 双向链表也可以配合下面的其他链表的扩展使用.

由于另外储存了指向链表内容的指针, 并且可能会修改相邻的节点, 有的时候第一个节点可能会被删除或者在之前添加一个新的节点. 这时候就要修改指向首个节点的指针. 有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后, 第一个节点之前储存一个永远不会被删除或者移动的虚拟节点, 形成一个下面说的循环链表. 这个虚拟节点之后的节点就是真正的第一个节点. 这种情况通常可以用这个虚拟节点直接表示这个链表, 对于把链表单独的存在数组 https://zh.wikipedia.org/wiki/数组里的情况, 也可以直接用这个数组表示链表并用第 0 个或者第 - 1 个 (如果编译器支持) 节点固定的表示这个虚拟节点.

@implementation DoubleLinkList
/**
 初始化一个双向链表
 @param node 链表的头节点
 @return 返回一个已初始化的双向链表
 */
- (instancetype)initWithNode:(DoubleLinkListNode *)node {
    self = [super init];
    if (self) {
        self.headNode = node;
    }
    return self;
}
/**
 判断链表是否为空
 @return 为空返回 YES, 反之为 NO
 */
- (BOOL)isEmpty {
    return self.headNode == nil;
}
/**
 获取链表拥有的总节点数
 @return 总节点数
 */
- (NSInteger)length {
    DoubleLinkListNode *cur = self.headNode;
    NSInteger count = 0;
    while (cur) {
        count++;
        cur = cur.nextNode;
    }
    return count;
}
/**
 遍历链表
 */
- (void)travel {
    // 空链表的情况
    if ([self isEmpty]) return;
    DoubleLinkListNode *cur = self.headNode;
    while (cur) {
        NSLog(@"%ld",cur.element);
        cur = cur.nextNode;
    }
}
// ============== 以上与单向链表完全一致 ==============================
/**
 头插法: 在链表的头部插入节点
 @param item 插入的元素
 */
- (void)insertNodeAtHeadWithItem:(NSInteger)item {
    DoubleLinkListNode *node = [[DoubleLinkListNode alloc] initWithItem: item];
    node.nextNode = self.headNode;
    // ===== 只加了这一句 =====
    self.headNode.prevNode = node;
    self.headNode = node;
}
/**
 尾插法: 在链表的尾部插入节点
 @param item 插入的元素
 */
- (void)appendNodeWithItem:(NSInteger)item {
    DoubleLinkListNode *node = [[DoubleLinkListNode alloc] initWithItem: item];
    if ([self isEmpty]) {
        self.headNode = node;
    }
    else {
        DoubleLinkListNode *cur = self.headNode;
        while (cur.nextNode) {
            cur = cur.nextNode;
        }
        cur.nextNode = node;
        // ===== 只加了这一句 =====
        node.prevNode = cur;
    }
}
/**
 指定位置插入节点
 @param item 插入的元素
 @param index 位置的索引
 */
- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index {
    if (index <= 0) {
        [self insertNodeAtHeadWithItem: item];
    }
    else if (index> ([self length] - 1)) {
        [self appendNodeWithItem: item];
    }
    else {
        DoubleLinkListNode *cur = self.headNode;
        for (int i = 0; i <index; i++) // i < index -1 改为 i < index
        {
            cur = cur.nextNode;
        }
        DoubleLinkListNode *node = [[DoubleLinkListNode alloc] initWithItem: item];
        node.nextNode = cur;
        node.prevNode = cur.prevNode;
        cur.prevNode.nextNode = node;
        cur.prevNode = node;
    }
}
/**
 删除节点
 @param item 删除的元素
 */
- (void)removeNodeWithItem:(NSInteger)item {
    DoubleLinkListNode *cur = self.headNode;
    while (cur != nil) {
        if (cur.element == item) {
            // 先判断此节点是不是头节点
            // 头节点
            if (cur == self.headNode) {
                // 如果链表只有一个节点那么 cur.nextNode == nil
                self.headNode = cur.nextNode;
                // cur.nextNode 不为空即表示链表不只有一个节点
                if (cur.nextNode) {
                    // 删除头节点后下一个节点的 prev 节点仍然储存着原头节点, 所以要置空
                    cur.nextNode.prevNode = nil;
                }
            }
            else {
                // 删除普通节点
                // 一, 让 cur 前一个节点的 next 连上 cur 后一个节点
                cur.prevNode.nextNode = cur.nextNode;
                // 二, 如果 cur 的后一个节点存在, 让 cur 后一个节点的 prev 连上 cur 前一个节点
                if (cur.nextNode) {
                    cur.nextNode.prevNode = cur.prevNode;
                }
                break;
            }
        }
        else {
            cur = cur.nextNode;
        }
    }
}
/**
 查询某个节点是否存在
 @param item 查询的元素
 @return 存在返回 YES, 反之为 NO
 */
- (BOOL)searchNodeWithItem:(NSInteger)item {
    DoubleLinkListNode *cur = self.headNode;
    while (cur != nil) {
        if (cur.element == item) {
            return YES;
        }
        else {
            cur = cur.nextNode;
        }
    }
    return NO;
}
@end

实际使用案例

// ViewDidLoad
- (void)viewDidLoad {
    [super viewDidLoad];
    DoubleLinkList *dll = [[DoubleLinkList alloc] initWithNode: nil];
//    NSLog(@"%d", [dll isEmpty]);
//    NSLog(@"%ld", [dll length]);
    [dll appendNodeWithItem: 1];
//    NSLog(@"%d", [dll isEmpty]);
//    NSLog(@"%ld", [dll length]);
    [dll appendNodeWithItem: 2];
    [dll insertNodeAtHeadWithItem: 8];
    [dll appendNodeWithItem: 3];
    [dll appendNodeWithItem: 4];
    [dll appendNodeWithItem: 5];
    [dll appendNodeWithItem: 6];
//    [dll travel]; // 8 1 2 3 4 5 6
    [dll insertNodeWithItem: 9 atIndex: -1];
//    [dll travel]; // 9 8 1 2 3 4 5 6
    [dll insertNodeWithItem: 100 atIndex: 3];
//    [dll travel]; // 9 8 1 100 2 3 4 5 6
    [dll insertNodeWithItem: 200 atIndex: 10];
//    [dll travel]; // 9 8 1 100 2 3 4 5 6 200
    [dll removeNodeWithItem: 100];
    [dll travel]; // 9 8 1 2 3 4 5 6 200
}

寡人的思路

双向链表的节点构成与单链表有一点区别: 多了一个 prevNode 前驱(前一个节点)

/**
   节点元素值
   */
  @property (nonatomic, assign) NSInteger element;
  /**
   下一个节点
   */
  @property (nonatomic, strong) DoubleLinkListNode *nextNode;
  /**
   前一个节点
   */
  @property (nonatomic, strong) DoubleLinkListNode *prevNode;

初始化一个双向链表: 与单向链表初始化思路完全一致

判断链表是否为空: 与单向链表思路完全一致

获取链表拥有的总节点数: 与单向链表思路完全一致

遍历链表: 与单向链表思路完全一致

头插法 -- 在链表的头部插入节点:

只加了一句代码: self.headNode.prevNode = node;, 这句代码旨在将新头节点的前驱 prevNode 与尾节点相连. 因为双向链表的节点多了前驱, 所以在头尾节点处理的时候要多处理一下.

尾插法 -- 在链表的尾部插入节点:

同样只加了一句代码: node.prevNode = cur;, 同样的, 这句代码是在处理新尾节点的前驱 prevNode , 让其与原尾节点相连.

指定位置插入节点:

与单向链表有两点不同:

循环次数不同 : 单向链表的循环次数为 index - 1 次, 双向链表的循环次数为 index 次. 造成不同的原因仍然是因为双向链表节点构成中多出了一个前驱 prevNode. 单向链表中没有前驱, 只能通过后继节点 nextNode 进行遍历, 所以循环次数要少一次, 为了让游标停在插入位置的前一个节点. 双向链表节点本身的构成中就拥有前驱属性, 所以可以干脆停在插入位置, 通过前驱 prevNode 和后继 nextNode 来进行遍历.

处理多出来的前驱: 双向链表插入的节点不但要处理与前一个节点和后一个节点的后继 nextNode 的关系, 还要处理与前一个节点和后一个节点的前驱 prevNode 的关系.

删除节点:

与单向链表仍然有两点不同:

循环条件不同 : 这与指定位置插入节点的循环次数不同原因一样.

处理多出来的前驱 : 需要注意两个位置, 一个是删除头节点后下一个节点的 prev 节点仍然储存着原头节点, 所以需要置空. 另外正常情况下, 如果 cur 的后一个节点存在, 让 cur 后一个节点的 prev 连上 cur 前一个节点.

查询某个节点是否存在: 与单向链表的逻辑基本一致, 唯一就是判断条件不同.

双向循环链表

双向循环链表的节点构成与双向链表相同, 包括节点元素 element , 前驱节点 prevNode , 后继节点 nextNode. 与双向链表不同的是双向循环链表的尾节点的后继节点 nextNode 要指向头节点, 头节点的前驱节点 prevNode 要指向尾节点, 以构成循环链表.

在下面的源码中, 有大量的语句与单向循环链表或双向链表相同, 只有少量的逻辑有差别. 与双向链表相比差别主要有以下几点:

双向循环链表要处理尾节点的后继节点与头节点的前驱节点.

双向循环链表在寻找尾节点或者说从头节点遍历到尾节点时的判断条件不同, 这是因为双向链表尾节点的后继节点指向 nil, 头节点的前驱节点也指向 nil, 它是不考虑 "首尾相连" 的. 而双向循环链表需要考虑所谓的 "首尾相连", 即头节点的前驱节点要指向尾节点, 尾节点的后继节点要指向头节点.

/**
 初始化一个双向循环链表
 @param node 链表的头节点
 @return 返回一个已初始化的双向循环链表
 */
- (instancetype)initWithNode:(DoubleCycleLinkListNode *)node {
    self = [super init];
    if (self) {
        self.headNode = node;
        // 判断 node 不为空的情况, 循环指向自己
        if (node) {
            node.nextNode = node;
            node.prevNode = node;
        }
    }
    return self;
}
/**
 判断链表是否为空
 @return 为空返回 YES, 反之为 NO
 */
- (BOOL)isEmpty {
    return self.headNode == nil;
}
/**
 获取链表拥有的总节点数
 @return 总节点数
 */
- (NSInteger)length {
    if ([self isEmpty]) return 0;
    DoubleCycleLinkListNode *cur = self.headNode;
    NSInteger count = 1;
    while (cur.nextNode != self.headNode) {
        count++;
        cur = cur.nextNode;
    }
    return count;
}
/**
 遍历链表
 */
- (void)travel {
    // 空链表的情况
    if ([self isEmpty]) return;
    DoubleCycleLinkListNode *cur = self.headNode;
    while (cur.nextNode != self.headNode) {
        NSLog(@"%ld", cur.element);
        cur = cur.nextNode;
    }
    // 退出循环, cur 指向尾节点, 但尾节点的元素未打印
    NSLog(@"%ld", cur.element);
}
/**
 头插法: 在链表的头部插入节点
 @param item 插入的元素
 */
- (void)insertNodeAtHeadWithItem:(NSInteger)item {
    DoubleCycleLinkListNode *node = [[DoubleCycleLinkListNode alloc] initWithItem:item];
    if ([self isEmpty]) {
        self.headNode = node;
        node.nextNode = node;
        node.prevNode = node;
    }
    else {
        DoubleCycleLinkListNode *cur = self.headNode;
        while (cur.nextNode != self.headNode) {
            cur = cur.nextNode;
        }
        /**
         * 退出循环后, cur 指向尾节点.
         * 因为是头插法, 所以 node 是新头节点
         */
        node.nextNode = self.headNode;  // node 向后是原 head
        self.headNode.prevNode = node;  // 原 head 向前是 node
        node.prevNode = cur;            // node 向前, 循环到尾节点
        cur.nextNode = node;            // 尾节点向后, 循环到现头节点 node
        self.headNode = node;
    }
}
/**
 尾插法: 在链表的尾部插入节点
 @param item 插入的元素
 */
- (void)appendNodeWithItem:(NSInteger)item {
    DoubleCycleLinkListNode *node = [[DoubleCycleLinkListNode alloc] initWithItem:item];
    if ([self isEmpty]) {
        self.headNode = node;
        node.nextNode = node;
        node.prevNode = node;
    }
    else {
        DoubleCycleLinkListNode *cur = self.headNode;
        while (cur.nextNode != self.headNode) {
            cur = cur.nextNode;
        }
        /**
         * 退出循环后, cur 指向尾节点.
         * 因为是尾插法, 所以 node 是新尾节点
         */
        cur.nextNode = node;            // 原尾节点 cur 向后是现尾节点 node
        node.prevNode = cur;            // 现尾节点 node 向前是原尾节点 cur
        node.nextNode = self.headNode;  // 现尾节点 node 向后, 循环到头节点
        self.headNode.prevNode = node;  // 头节点向前, 循环到现尾节点 node
    }
}
/**
 指定位置插入节点
 @param item 插入的元素
 @param index 位置的索引
 */
- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index {
    if (index <= 0) {
        [self insertNodeAtHeadWithItem: item];
    }
    else if (index> ([self length] - 1)) {
        [self appendNodeWithItem: item];
    }
    else {
        DoubleCycleLinkListNode *cur = self.headNode;
        NSInteger count = 0;
        while (count < index) {
            count++;
            cur = cur.nextNode;
        }
        /*
         * 当循环退出后, cur 指向 index 位置
         * cur 是原 index 位置节点
         * node 是现 index 位置节点
         */
        DoubleCycleLinkListNode *node = [[DoubleCycleLinkListNode alloc] initWithItem:item];
        node.nextNode = cur;            // node 向后是 cur
        node.prevNode = cur.prevNode;   // 未修改 cur 的 prevNode 前, node 向前是 cur 的 prevNode
        cur.prevNode.nextNode = node;   // 未修改 cur 的 prevNode 前, cur 的 prevNode 向后是 node
        cur.prevNode = node;            // 修改了 cur 的 prevNode 后, cur 向前是 node
    }
}
/**
 删除节点
 @param item 删除的元素
 */
- (void)removeNodeWithItem:(NSInteger)item {
    if ([self isEmpty]) return;
    DoubleCycleLinkListNode *cur = self.headNode;
    while (cur.nextNode != self.headNode) {
        if (cur.element == item) {
            // 1. 删除头节点的情况
            if (cur == self.headNode) {
                // 先找到尾节点
                DoubleCycleLinkListNode *tail = self.headNode;
                while (tail.nextNode != self.headNode) {
                    tail = tail.nextNode;
                }
                // 循环结束后, tail 指向当前尾节点
                self.headNode = cur.nextNode;   // cur 就是头节点. 让头节点指向其下一节点, 即删除头节点
                self.headNode.prevNode = tail;  // 新头节点向前, 循环到尾节点 rear
                tail.nextNode = self.headNode;  // 尾节点 rear 向后, 循环到新头节点
            }
            // 2. 删除非头节点的情况
            else {
                cur.prevNode.nextNode = cur.nextNode;   // 看图解析
                cur.nextNode.prevNode = cur.prevNode;   // 看图解析
            }
            return;
        }
        else {
            cur = cur.nextNode;
        }
        // 退出循环, cur 指向尾节点
        if (cur.element == item) {
            if (cur == self.headNode) {
                // 如果 cur 指向头节点, 证明链表只有一个节点
                self.headNode = nil;
            }
            else {
                cur.prevNode.nextNode = cur.nextNode;   // 看图解析
                cur.nextNode.prevNode = cur.prevNode;   // 看图解析
            }
        }
    }
}
/**
 查询某个节点是否存在
 @param item 查询的元素
 @return 存在返回 YES, 反之为 NO
 */
- (BOOL)searchNodeWithItem:(NSInteger)item {
    if ([self isEmpty]) return NO;
    DoubleCycleLinkListNode *cur = self.headNode;
    while (cur.nextNode != self.headNode) {
        if (cur.element == item) {
            return YES;
        }
        else {
            cur = cur.nextNode;
        }
    }
    // 退出循环, cur 指向尾节点
    if (cur.element == item) {
        return YES;
    }
    return NO;
}
@end

实际使用案例

// ViewController
- (void)viewDidLoad {
    [super viewDidLoad];
    DoubleCycleLinkList *dcll = [[DoubleCycleLinkList alloc] init];
//    NSLog(@"%d", [dcll isEmpty]); // 1
//    NSLog(@"%ld", [dcll length]); // 0
    [dcll appendNodeWithItem: 1];
//    NSLog(@"%d", [dcll isEmpty]); // 0
//    NSLog(@"%ld", [dcll length]); // 1
    [dcll appendNodeWithItem: 2];
    [dcll insertNodeAtHeadWithItem:8];
    [dcll appendNodeWithItem: 3];
    [dcll appendNodeWithItem: 4];
//    [dcll travel]; // 8 1 2 3 4
    [dcll insertNodeWithItem:9 atIndex:-1];
//    [dcll travel]; // 9 8 1 2 3 4
    [dcll insertNodeWithItem:100 atIndex:3];
//    [dcll travel]; // 9 8 1 100 2 3 4
    [dcll insertNodeWithItem:200 atIndex:10];
//    [dcll travel]; // 9 8 1 100 2 3 4 200
    [dcll removeNodeWithItem:9];
//    [dcll travel]; // 8 1 100 2 3 4 200
    [dcll removeNodeWithItem:100];
//    [dcll travel]; // 8 1 2 3 4 200
    [dcll removeNodeWithItem:200];
    [dcll travel]; // 8 1 2 3 4
    NSLog(@"result:%d", [dcll searchNodeWithItem:100]);
}

GitHub 完整源码

双向链表 - GCDoubleLinkList https://github.com/ChinaChong/GCDoubleLinkList

双向循环链表 - GCDoubleCycleLinkList

参考资料

双向链表 - 维基百科, 自由的百科全书

链表 - 维基百科, 自由的百科全书

来源: http://www.jianshu.com/p/a68616ba54d5

与本文相关文章

暂无,快来抢沙发吧！