單鏈表具有單向性的缺點，找前驅不方便！

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。

image.png

image.png

創(chuàng)建一個節(jié)點，節(jié)點包含前節(jié)點，后節(jié)點，本節(jié)點的key和value
/**
 節(jié)點信息
 */
@interface TwoWayLinkedListNode : NSObject
{
    @package
    __unsafe_unretained TwoWayLinkedListNode *_prior; // retained by dic
    __unsafe_unretained TwoWayLinkedListNode *_next; // retained by dic
    id _key;
    id _value;
}
@end

@implementation TwoWayLinkedListNode
@end

/**
 鏈表
 */
@interface TwoWayLinkedList ()
{
    @package
    TwoWayLinkedListNode *_head; // 鏈表頭
    TwoWayLinkedListNode *_tail; // 鏈表尾
    
    NSMutableDictionary  *_dic;  // 鏈表字典

}
@end

@implementation TwoWayLinkedList

- (instancetype)init
{
    self = [super init];
    if (self) {
        _dic = [NSMutableDictionary dictionary];
    }
    return self;
}

• 在最前端添加一個節(jié)點

/**
 在最前端添加一個節(jié)點

 @param node node
 */
- (void)insertNodeAtHead:(TwoWayLinkedListNode *)node {
    [_dic setObject:node forKey:node->_key];
    
    if (_head) {
        node->_next = _head;
        _head->_prior = node;
        _head = node;
    }
    else {
        _head = _tail = node;
    }
}

• 將某個節(jié)點移到最前端

/**
 將某個節(jié)點移到最前端

 @param node node
 */
- (void)bringNodeToHead:(TwoWayLinkedListNode *)node {
    if (_head == node) {
        return;
    }
    if (_tail == node) {
        /*
         條件:node節(jié)點是tail節(jié)點時
         將node節(jié)點的前一個節(jié)點變成tail節(jié)點
         tail節(jié)點的next置空
         */
        _tail = node->_prior;
        _tail->_next = nil;
    }
    else {
        /*
         條件:node節(jié)點是中間節(jié)點時
         將node的前一個節(jié)點賦值給node的下一個節(jié)點的prev
         將node的下一個節(jié)點賦值給node的前一個節(jié)點
         */
        node->_next->_prior = node->_prior;
        node->_prior->_next = node->_next;
    }
    
    // 將node移動到head節(jié)點并且將原h(huán)ead節(jié)點的放到head->next節(jié)點中
    node->_next = _head;
    node->_prior = nil;
    _head->_prior = node;
    _head = node;
}

• 刪除某個節(jié)點

/**
 刪除某個節(jié)點

 @param node 節(jié)點
 */
- (void)removeNode:(TwoWayLinkedListNode *)node {
    [_dic removeObjectForKey:node->_key];
    
    if (node->_next) {
        node->_next->_prior = node->_prior;
    }
    
    if (node->_prior) {
        node->_prior->_next = node->_next;
    }
    
    if (_head == node) {
        _head = node->_next;
    }
    
    if (_tail == node) {
        _tail = node->_prior;
    }
}

• 清空鏈表

/**
 清空鏈表
 */
- (void)removeAll {
    _head = nil;
    _tail = nil;
    
    _dic = [NSMutableDictionary dictionaryWithCapacity:0];
}

擴展1
最近最久未使用算法

每次將使用到的節(jié)點移動到最前方實現(xiàn)LRU算法

 TwoWayLinkedList *list = [[TwoWayLinkedList alloc]init];

    if (node) {
        [list bringNodeToHead:node];
    } else {
        [list insertNodeAtHead:node];
    }

擴展2
將鏈表就地逆置

image.png

插入法：掃描a1……an, 將每個ai插入到鏈表首部即可。

image.png