本文共 4193 字，大约阅读时间需要 13 分钟。

Objective-C 实现带头双向循环链表

在 Objective-C 中实现一个带头的双向循环链表（Doubly Circular Linked List），我们需要创建一个节点类和一个链表类。以下是一个简单的实现，包含基本的操作，如插入、删除和遍历。

节点类

节点类是链表的基础，通常包含以下属性：

• 数据（data）：存储节点的数据。
• 下一个指针（next）：指向下一个节点。
• 上一个指针（previous）：指向上一个节点。

链表类

链表类负责管理链表的逻辑，通常包含以下方法：

• 插入节点（insert）
• 删除节点（delete）
• 遍历链表（traverse）
• 检索节点（retrieve）

链表的结构

链表的带头结构如下：

*----> *--

其中，head 是链表的开头节点，tail 是链表的结尾节点。同时，head 和 tail 节点各自指向最后一个节点，形成双向循环。

实现步骤

节点类在 Objective-C 中可以通过接口（protocol）和实现（protocol implementation）来实现。代码如下：

@import Foundation

@interface Node : NSObject

@property (nonatomic, strong) id data;@property (nonatomic, weak) Node *next;@property (nonatomic, weak) Node *previous;

@end

2. 创建链表类

链表类负责管理链表的逻辑，代码如下：

@import Foundation

@interface List : NSObject

@property (nonatomic, strong) Node *head;@property (nonatomic, strong) Node *tail;

• (Node *)insert:(Node *)node;
• (Node *)delete:(Node *)node;
• (void)traverse;
• (Node *)retrieve:(id)key;

@end

3. 实现链表操作

链表操作分为插入、删除和遍历三类。

插入节点

插入节点需要根据给定的键值创建节点对象，并将其插入链表的适当位置。

• (Node *)insert:(id)key {Node *newNode = [[Node alloc] init];newNode.data = key;if (newNode.data == nil) return nil;

  if (self.head == nil) {newNode.previous = newNode;newNode.next = newNode;self.head = newNode;self.tail = newNode;} else {Node *current = self.head;while (current != nil && current.data < newNode.data) {current = current.next;}if (current == nil) {newNode.previous = self.tail;newNode.next = self.tail.next;self.tail.next = newNode;self.tail = newNode;} else {newNode.previous = current.previous;newNode.next = current;current.previous = newNode;}}return newNode;}

删除节点

删除节点需要根据给定的键值找到节点，并移除它。

• (Node *)delete:(id)key {Node *node = [self retrieve:key];if (node == nil) return nil;

  if (node == self.head) {self.head = node.next;if (self.head != nil) {self.head.previous = nil;} else {self.tail = nil;}} else if (node == self.tail) {self.tail = node.previous;if (self.tail != nil) {self.tail.next = nil;} else {self.head = nil;}} else {Node *previousNode = node.previous;Node *nextNode = node.next;previousNode.next = nextNode;nextNode.previous = previousNode;}return node;}

遍历链表

遍历链表需要从头节点开始，依次访问每个节点。

• (void)traverse {Node *current = self.head;while (current != nil) {NSLog(@"当前节点数据：%@", current.data);current = current.next;}}

检索节点

检索节点需要根据键值找到对应的节点。

• (Node *)retrieve:(id)key {Node *current = self.head;while (current != nil) {if (current.data == key) {return current;}current = current.next;}return nil;}

完整代码示例

将以上代码整合起来，得到完整的类实现：

@import Foundation

@interface Node : NSObject

@property (nonatomic, strong) id data;@property (nonatomic, weak) Node *next;@property (nonatomic, weak) Node *previous;

@end

@interface List : NSObject

@property (nonatomic, strong) Node *head;@property (nonatomic, strong) Node *tail;

• (Node *)insert:(id)key;
• (Node *)delete:(id)key;
• (void)traverse;
• (Node *)retrieve:(id)key;

@end

@implementation Node

@end

@implementation List

• (Node *)insert:(id)key {Node *newNode = [[Node alloc] init];newNode.data = key;if (newNode.data == nil) return nil;

  if (self.head == nil) {newNode.previous = newNode;newNode.next = newNode;self.head = newNode;self.tail = newNode;} else {Node *current = self.head;while (current != nil && current.data < newNode.data) {current = current.next;}if (current == nil) {newNode.previous = self.tail;newNode.next = self.tail.next;self.tail.next = newNode;self.tail = newNode;} else {newNode.previous = current.previous;newNode.next = current;current.previous = newNode;}}return newNode;}

• (Node *)delete:(id)key {Node *node = [self retrieve:key];if (node == nil) return nil;

  if (node == self.head) {self.head = node.next;if (self.head != nil) {self.head.previous = nil;} else {self.tail = nil;}} else if (node == self.tail) {self.tail = node.previous;if (self.tail != nil) {self.tail.next = nil;} else {self.head = nil;}} else {Node *previousNode = node.previous;Node *nextNode = node.next;previousNode.next = nextNode;nextNode.previous = previousNode;}return node;}

• (void)traverse {Node *current = self.head;while (current != nil) {NSLog(@"当前节点数据：%@", current.data);current = current.next;}}

• (Node *)retrieve:(id)key {Node *current = self.head;while (current != nil) {if (current.data == key) {return current;}current = current.next;}return nil;}

@end

转载地址：http://coifk.baihongyu.com/