最近有点手痒,然后写了个双向循环链表
image.png
1.建立LinkList,分别用frist和last引用头尾节点
2.为了防止循环引用,节点间的引用previous和next必须有一个由weak引用,这样在断掉LinkList的引用和断掉尾节的next的引用时,整个链表就可以释放了
@interface GYJCircleLinkList : NSObject
//获取链表中存储元素的个数
- (NSInteger)size;
//获取元素列表是否为空
- (BOOL)isEmpty;
//添加元素
- (void)addElement:(NSObject *)element;
//在某位置插入元素
- (void)insertElement:(NSObject *)element atIndex:(NSInteger)index;
//移除某索引下元素
- (NSObject *)removeObjcAtIndex:(NSInteger)index;
//替换某索引下元素
- (NSObject *)replaceElementByNewElement:(NSObject *)newElement index:(NSInteger)index;
//是否含有给定元素
- (BOOL)containsElement:(NSObject *)element;
//获取索引下标,如果没找到,返回-1
- (NSInteger)indexOfElement:(NSObject *)element;
//返回索引下的内容
- (NSObject *)elementOfIndex:(NSInteger)index;
//清空链表
- (void)clear;
- (NSString *)toString;
@end
///节点
@interface GYJNode : NSObject
@property(nonatomic,strong,nullable)GYJNode *nextNode;
@property(nonatomic,weak,nullable)GYJNode *previousNode;
@property(nonatomic,strong)NSObject *element;
- (instancetype)initWithPreviousNode:(nullable GYJNode *)previous Element:(NSObject *)element nextNode:(nullable GYJNode *)nextNode;
- (NSString *)toString;
@end
#import "GYJCircleLinkList.h"
@interface GYJCircleLinkList ()
@property(nonatomic,assign)NSInteger size;
@property(nonatomic,strong)GYJNode *frist;
@property(nonatomic,strong)GYJNode *last;
@end
static const NSInteger ELEMENT_NOT_FOUND = -1;
@implementation GYJCircleLinkList
- (NSInteger)size;
{
return _size;
}
- (BOOL)isEmpty{
return _size == 0;
}
- (void)addElement:(NSObject *)element{
[self insertElement:element atIndex:_size];
}
- (void)insertElement:(NSObject *)element atIndex:(NSInteger)index
{
[self indexOfAddRange:index];
if (_frist==nil) {
GYJNode *newNode = [[GYJNode alloc]initWithPreviousNode:nil Element:element nextNode:nil];
_frist = newNode;
_last = newNode;
newNode.previousNode = newNode;
newNode.nextNode = newNode;
}else{
GYJNode *lastNode = [self searchNodeUseIndex:_size-1];
GYJNode *headNode = lastNode.nextNode;
GYJNode *newNode = [[GYJNode alloc]initWithPreviousNode:lastNode Element:element nextNode:headNode];
lastNode.nextNode = newNode;
headNode.previousNode = newNode;
_last = newNode;
}
_size++;
}
- (NSObject *)removeObjcAtIndex:(NSInteger)index{
[self indexOutOfRange:index];
if (_frist == nil) {
return nil;
}
GYJNode *node = [self searchNodeUseIndex:index];
if (_size==1) {
node.nextNode = nil;
_frist = nil;
_last = nil;
_size = 0;
}else{
if (index==0) {
_frist = node.nextNode;
_last.nextNode = node.nextNode;
node.nextNode.previousNode = _last;
node.nextNode = nil;
}else if (index==_size-1){
_last = node.previousNode;
_frist.previousNode = _last;
node.previousNode.nextNode = _frist;
node.nextNode = nil;
}else{
GYJNode *prevoisNode = node.previousNode;
prevoisNode.nextNode = node.nextNode;
node.nextNode.previousNode = prevoisNode;
node.nextNode = nil;
}
_size--;
}
return node.element;
}
- (NSObject *)replaceElementByNewElement:(NSObject *)newElement index:(NSInteger)index{
[self indexOutOfRange:index];
GYJNode *node = [self searchNodeUseIndex:index];
if (node==nil) {
return nil;
}
NSObject *oldElement = node.element;
node.element = newElement;
return oldElement;
}
- (BOOL)containsElement:(NSObject *)element
{
return [self indexOfElement:element]==ELEMENT_NOT_FOUND?NO:YES;
}
- (NSInteger)indexOfElement:(NSObject *)element{
if (element==nil) {
GYJNode *node = _frist;
for (NSInteger i = 0; i<_size; i++) {
if (node.element == nil) {
return I;
}
node = node.nextNode;
}
}else{
GYJNode *node = _frist;
for (NSInteger i = 0; i<_size; i++) {
if ([node.element isEqual:element]) {
return I;
}
node = node.nextNode;
}
}
return ELEMENT_NOT_FOUND;
}
- (NSObject *)elementOfIndex:(NSInteger)index{
[self indexOutOfRange:index];
GYJNode *node = [self searchNodeUseIndex:index];
return node.element;
}
- (void)clear{
if (_last==nil) {
return;
}else{
_last.nextNode = nil;
_frist = nil;
_last = nil;
}
_size = 0;
}
- (nullable GYJNode *)searchNodeUseIndex:(NSInteger)index
{
[self indexOutOfRange:index];
GYJNode *mark = _frist;
if (index<(_size>>1)) {
for (NSInteger i = 0; i<index; i++) {
mark = mark.nextNode;
}
return mark;
}else{
if (_frist==nil) {
return nil;
}else{
mark = _last;
for (NSInteger i = _size-1; i>index; i--) {
mark = mark.previousNode;
}
return mark;
}
}
return nil;
}
- (void)indexOutOfRange:(NSInteger)index{
BOOL res = index<0||index>_size-1;
NSAssert(res==NO, @"传入的index超出链表索引");
}
- (void)indexOfAddRange:(NSInteger)index{
BOOL res = index<0||index>_size;
NSAssert(res==NO, @"传入的index超出链表索引");
}
- (NSString *)toString
{
NSMutableString *string = [[NSMutableString alloc]init];
GYJNode *node = _frist;
[string appendString:[NSString stringWithFormat:@"size=%ld",_size]];
[string appendString:@"["];
for (NSInteger i = 0; i<_size; i++) {
if (i!=0) {
[string appendString:@","];
}
[string appendString:[node toString]];
node = node.nextNode;
}
[string appendString:@"]"];
return string.copy;
}
@end
@implementation GYJNode
- (instancetype)initWithPreviousNode:(nullable GYJNode *)previous Element:(NSObject *)element nextNode:(nullable GYJNode *)nextNode
{
if (self = [super init]) {
_previousNode = previous;
_nextNode = nextNode;
_element = element;
}
return self;
}
- (NSString *)toString
{
NSMutableString *string = [[NSMutableString alloc]init];
[string appendString:[NSString stringWithFormat:@"%@_%@_%@",_previousNode.element,_element,_nextNode.element]];
return string.copy;
}
- (void)dealloc
{
NSLog(@"元素释放了:%@_%@_%@",_previousNode.element,_element,_nextNode.element);
}
@end
测试代码
GYJCircleLinkList *linkList = [[GYJCircleLinkList alloc]init];
for (NSInteger i = 1; i<10; i++) {
[linkList addElement:@(i)];
}
NSLog(@"%@",[linkList toString]);
[linkList removeObjcAtIndex:0]; //size=8 [9_2_3,2_3_4,3_4_5,4_5_6,5_6_7,6_7_8,7_8_9,8_9_2]
[linkList removeObjcAtIndex:[linkList size]-1];//size=7 [8_2_3,2_3_4,3_4_5,4_5_6,5_6_7,6_7_8,7_8_2]
[linkList removeObjcAtIndex:1];// size=6 [8_2_4,2_4_5,4_5_6,5_6_7,6_7_8,7_8_2]
NSLog(@"%@",[linkList toString]);
[linkList replaceElementByNewElement:@(100) index:3]; //size=6 [8_2_4,2_4_5,4_5_6,5_100_7,6_7_8,7_8_2]
NSLog(@"%@",[linkList toString]);
[linkList elementOfIndex:5]; //7
NSInteger number = [linkList indexOfElement:@(5)]; //size=6 [8_2_4,2_4_5,4_5_100,5_100_7,100_7_8,7_8_2]
NSLog(@"%ld",number); //2
NSLog(@"containElement(%@) = %@",@(100),[linkList containsElement:@(100)]==YES?@"true":@"false");
[linkList clear]; //2,4,5,100,7,8
NSLog(@"%@",[linkList toString]);
最后打印结果显示链表的引用关系正常,对象也正常释放,可以像数组一样使用哈
2022-04-18 17:28:16.300819+0800 CompleteBinaryTree[19209:313617] size=9[9_1_2,1_2_3,2_3_4,3_4_5,4_5_6,5_6_7,6_7_8,7_8_9,8_9_1]
2022-04-18 17:28:16.301134+0800 CompleteBinaryTree[19209:313617] 元素释放了:9_1_(null)
2022-04-18 17:28:16.301378+0800 CompleteBinaryTree[19209:313617] 元素释放了:8_9_(null)
2022-04-18 17:28:16.301581+0800 CompleteBinaryTree[19209:313617] 元素释放了:2_3_(null)
2022-04-18 17:28:16.301836+0800 CompleteBinaryTree[19209:313617] size=6[8_2_4,2_4_5,4_5_6,5_6_7,6_7_8,7_8_2]
2022-04-18 17:28:16.302104+0800 CompleteBinaryTree[19209:313617] size=6[8_2_4,2_4_5,4_5_100,5_100_7,100_7_8,7_8_2]
2022-04-18 17:28:16.302262+0800 CompleteBinaryTree[19209:313617] 2
2022-04-18 17:28:16.302430+0800 CompleteBinaryTree[19209:313617] containElement(100) = true
2022-04-18 17:28:16.302633+0800 CompleteBinaryTree[19209:313617] 元素释放了:8_2_4
2022-04-18 17:28:16.302819+0800 CompleteBinaryTree[19209:313617] 元素释放了:(null)_4_5
2022-04-18 17:28:16.303055+0800 CompleteBinaryTree[19209:313617] 元素释放了:(null)_5_100
2022-04-18 17:28:16.303364+0800 CompleteBinaryTree[19209:313617] 元素释放了:(null)_100_7
2022-04-18 17:28:16.303722+0800 CompleteBinaryTree[19209:313617] 元素释放了:(null)_7_8
2022-04-18 17:28:16.304106+0800 CompleteBinaryTree[19209:313617] 元素释放了:(null)_8_(null)
2022-04-18 17:28:16.304476+0800 CompleteBinaryTree[19209:313617] size=0[]
2022-04-18 17:28:16.333057+0800 CompleteBinaryTree[19209:313617] [UIFocus] Focus system enabled
附上 swift版本的双向链表,已经过测试
import Foundation
enum GYJError:Error{
case outOfBounds(Int,Int,String)
case wrongArgument(String)
case otherError
}
class GYJLinkedList<E:Equatable> {
// MARK : 公开的内容
///获取链表元素的个数
private(set) var size = 0
private var head : GYJNode<E>?
private var tail : GYJNode<E>?
///判断链表是否为空
func isEmpty() -> Bool{
return size == 0
}
///给链表添加元素
func addElement(_ element:E){
insertElement(element: element, index: size)
}
///在链表索引处插入元素
func insertElement(element: E,index : Int) {
assert(index>=0 && index <= size, "插入元素的索引越界")
let node = GYJNode(element)
if head == nil{
head = node
tail = node
}else if index == 0{
node.next = head
head?.previous = node
head = node
}else if index == size{
tail?.next = node
node.previous = tail
tail = node
}else{
let half = size >> 1
if index < half {
var currentNode = head
for _ in 1...index{
currentNode = currentNode?.next
}
let nextNode = currentNode?.next
node.next = nextNode
nextNode?.previous = node
node.previous = currentNode
currentNode?.next = node
}else{
var previous = tail
for _ in index..<size{
previous = previous?.previous
}
let nextNode = previous?.next
node.next = nextNode
nextNode?.previous = node
previous?.next = node
node.previous = previous
}
}
size += 1
}
///移除链表索引下的元素
@discardableResult
func removeElment(index : Int) -> E?{
assert(index>=0 && index < size, "插入元素的索引越界")
var node : GYJNode<E>?
if size == 1 {
node = head
head = nil
tail = nil
size -= 1
return node?.element
}
if index == 0{
let next = head?.next
node = head
head?.next = nil
head = next
}else if index == size-1{
node = tail
let previous = tail?.previous
previous?.next = nil
tail = previous
}else{
let half = size >> 1
if index < half{
node = head
for _ in 1...index{
node = node?.next
}
let next = node?.next
node?.previous?.next = next
}else{
node = tail
for _ in index..<(size-1){
node = node?.previous
}
let next = node?.next
node?.previous?.next = next
next?.previous = node?.previous
}
}
size -= 1
return node?.element
}
///移除链表中第一个符合相同条件的元素
@discardableResult
func removeElment(_ element : E) -> Bool{
let index = indexOfElment(element)
if index == nil {
return false
}else{
removeElment(index: index!)
return true
}
}
///获取index = 0的元素
func headElement() -> E?{
return head?.element
}
///获取最后一个元素
func tailElement() -> E?{
return tail?.element
}
///是否含有元素
func containsElment(_ element: E) -> Bool{
if indexOfElment(element) == nil{
return false
}
return true
}
func removeAllElement() {
head = nil
tail = nil
size = 0
}
// MARK : 私有的内容
private func indexOfElment(_ elment: E) -> Int?{
var node = head
for i in 0..<size{
if node?.element == elment{
return i
}
node = node?.next
}
return nil
}
/*
do{
try linkedList.insertElement(index: 2)
}catch GYJError.outOfBounds(_, _, let msg){
print(msg)
}catch{
}
func insertElement(index : Int) throws{
if index < 0 || index > size{
throw GYJError.outOfBounds(index, size, "链表越界")
}
/*
....代码内容
*/
}
*/
}
extension GYJLinkedList : CustomStringConvertible{
var description: String{
var str = ""
var node = head
while node != nil{
str.append(", ")
str.append(node!.previous?.description ?? "null_")
str.append(node!.description)
str.append(node!.next?.description ?? "_null")
node = node?.next
}
return str
}
}
private class GYJNode<E> : CustomStringConvertible{
var next: GYJNode?
weak var previous: GYJNode?
var element: E
init(_ elem: E){
element = elem
}
var description: String{
"_\(element)_"
}
deinit{
print("_\(element)_释放了")
}
}
