用OC实现双向链表：构造链表、插入节点、删除节点、遍历节点

// DoubleLinkNode.h
// LinkListDemo
// Created by 夏远全 on 2019/9/24.
#import <Foundation/Foundation.h>NS_ASSUME_NONNULL_BEGIN@interface DoubleLinkNode : NSObject
@property (nonatomic, assign) int data; //数据域
@property (nonatomic, weak, nullable) DoubleLinkNode *pre; //前驱指针域(防止循环引用)
@property (nonatomic, strong, nullable) DoubleLinkNode *next;//后继指针域
+(instancetype)constructNodeWithData:(int)data;
@end 

// DoubleLinkNode.m
// LinkListDemo
// Created by 夏远全 on 2019/9/24.
#import "DoubleLinkNode.h"@implementation DoubleLinkNode+(instancetype)constructNodeWithData:(int)data { DoubleLinkNode *node = [[DoubleLinkNode alloc] init];
node.data = data;
node.next = nil;
node.pre = nil;
return node;
}
@end

//1、构建一个双向链表
DoubleLinkNode *head = [[DoubleLinkNode alloc] init];
DoubleLinkNode *node1 = [DoubleLinkNode constructNodeWithData:];
DoubleLinkNode *node2 = [DoubleLinkNode constructNodeWithData:];
DoubleLinkNode *node3 = [DoubleLinkNode constructNodeWithData:];
head.next = node1;
node1.next = node2;
node1.pre = head;
node2.next = node3;
node2.pre = node1;
node3.pre = node2;
[FuncontionHandler printFromHeadWithNode:head printPrefixText:@"构造双向链表为"];

-- ::43.449741+ LinkList[:] 构造双向链表为：⇄⇄

//双向链表：在头部插入节点
+(void)insetNodeAfterHead:(DoubleLinkNode *)newNode headNode:(DoubleLinkNode *)headNode { //判空处理
if (!headNode) {
return;
} if (headNode.next == nil) {
headNode.next = newNode;
newNode.pre = headNode;
}
else{
newNode.next = headNode.next; //当前节点后继指向的头结点后继
newNode.pre = headNode; //当前节点的前驱指向头结点
headNode.next.pre = newNode; //头结点的后继结点的前驱指向当前节点
headNode.next = newNode; //头结点的后继指向当前节点
}
}

//从头部插入
DoubleLinkNode *node4 = [DoubleLinkNode constructNodeWithData:];
[FuncontionHandler insetNodeAfterHead:node4 headNode:head];
[FuncontionHandler printFromHeadWithNode:head printPrefixText:@"在双向链表头部插入节点4后"];

-- ::43.449741+ LinkList[:] 构造双向链表为：⇄⇄
-- ::43.450118+ LinkList[:] 在双向链表头部插入节点4后：⇄⇄⇄

//双向链表：在尾部插入节点
+(void)insetNodeAfterTail:(DoubleLinkNode *)newNode headNode:(DoubleLinkNode *)headNode { //判空处理
if (!headNode) {
return;
} //设置偏移指针
DoubleLinkNode *pNode = headNode;
while (pNode.next != nil) {
pNode = pNode.next;
}
pNode.next = newNode;
newNode.pre = pNode;
}

//从尾部插入
DoubleLinkNode *node5 = [DoubleLinkNode constructNodeWithData:];
[FuncontionHandler insetNodeAfterTail:node5 headNode:head];
[FuncontionHandler printFromHeadWithNode:head printPrefixText:@"在双向链表尾部插入节点5后"];

-- ::43.449741+ LinkList[:] 构造双向链表为：⇄⇄
-- ::43.450118+ LinkList[:] 在双向链表头部插入节点4后：⇄⇄⇄
-- ::43.450209+ LinkList[:] 在双向链表尾部插入节点5后：⇄⇄⇄⇄

//双向链表：在指定位置插入节点
+(void)insetNodeAtIndex:(int)k node:(DoubleLinkNode *)newNode headNode:(DoubleLinkNode *)headNode { //判空处理
if (!headNode) {
return;
} //设置偏移指针
DoubleLinkNode *pNode = headNode;
int i = ;
while (pNode!= nil && i<k) {
pNode = pNode.next;
i++;
}
if (i==k) {
//与从头结点插入的方式是一样的方法
newNode.next = pNode.next;
newNode.pre = pNode;
pNode.next.pre = newNode;
pNode.next = newNode;
}
}

//从指定位置插入
DoubleLinkNode *node6 = [DoubleLinkNode constructNodeWithData:];
[FuncontionHandler insetNodeAtIndex: node:node6 headNode:head];
[FuncontionHandler printFromHeadWithNode:head printPrefixText:@"在双向链表第2个位置插入节点6后"];

-- ::43.449741+ LinkList[:] 构造双向链表为：⇄⇄
-- ::43.450118+ LinkList[:] 在双向链表头部插入节点4后：⇄⇄⇄
-- ::43.450209+ LinkList[:] 在双向链表尾部插入节点5后：⇄⇄⇄⇄
-- ::43.450262+ LinkList[:] 在双向链表第2个位置插入节点6后：⇄⇄⇄⇄⇄

//双向链表：删除第k个位置的节点
+(DoubleLinkNode *)deleteNodeAtIndex:(int)k headNode:(DoubleLinkNode *)headNode { //判空处理
if (!headNode) {
return nil;
} //设置偏移指针
DoubleLinkNode *pNode = headNode.next;
int i = ;
while (pNode!= nil && i<k) {
pNode = pNode.next;
i++;
}
if (i==k) {
pNode.pre.next = pNode.next; //当前节点的前驱节点的后继指向当前节点的后继结点
pNode.next.pre = pNode.pre; //当前节点的后继结点的前驱指向当前节点的前驱节点
return pNode;
}
return nil;
}

//3、删除节点
DoubleLinkNode *deleteNode = [FuncontionHandler deleteNodeAtIndex: headNode:head];
NSString *prefixText = [NSString stringWithFormat:@"删除第2个位置的节点%d后单链表为",deleteNode.data];
[FuncontionHandler printFromHeadWithNode:head printPrefixText:prefixText];

-- ::43.449741+ LinkList[:] 构造双向链表为：⇄⇄
-- ::43.450118+ LinkList[:] 在双向链表头部插入节点4后：⇄⇄⇄
-- ::43.450209+ LinkList[:] 在双向链表尾部插入节点5后：⇄⇄⇄⇄
-- ::43.450262+ LinkList[:] 在双向链表第2个位置插入节点6后：⇄⇄⇄⇄⇄
-- ::43.450336+ LinkList[:] 删除第2个位置的节点6后单链表为：⇄⇄⇄⇄

//双向链表：遍历并打印链表
+(void)printFromHeadWithNode:(DoubleLinkNode *)headNode printPrefixText:(NSString *)text { //判空处理
if (!headNode) {
return;
} DoubleLinkNode *pNode = headNode.next;
NSMutableArray *items = [NSMutableArray array];
while (pNode!= nil) {
[items addObject:@(pNode.data)];
pNode = pNode.next;
}
NSLog(@"%@：%@",text,[items componentsJoinedByString:@"⇄"]);
}