それを回避する方法があります。実際には、すべてのポインターを 1 つの場所で追跡する必要はまったくありません。これは、Node
s 自体がデータ構造であるためです。
編集: Objective-C のコメントを見ました。
必要がありますNode
(Objective-C 構文):
// the actual info at this list index
@property (retain) id ptr;
@property (retain) Node *previous;
@property (retain) Node *next;
そして、あなたのDLL
クラスは単に次のクラスです。
@property (retain) Node *first;
@property (retain) Node *last;
@property (assign) NSUInteger count;
それだけです。Node の挿入または削除には、ポインターのシャッフルとcount
調整が必要であり、アクセスはどちらかの端から順番に行われます。
add:(Node*)newNode
文字通り次のようになります。
[newNode setPrevious:[self last]];
[[self last] setNext:newNode];
[self setLast:newNode];
[self setCount:[self count]+1];
..一方add:(Node*)newNode atIndex:(NSUInteger)index
、もう少し複雑になります:
if(index > self.count)
{
// maybe throw an exception or something
} else if(index == self.count) // just do the normal add
{
[self add:newNode];
return;
} else if(index == 0) { // front-insert is also easier
[newNode setNext:[self first]];
[[self first] setPrevious:newNode];
[self setFirst:newNode];
[self setCount:[self count]+1];
return;
}
// maybe do an extra check to see if it's quicker to search from the end
Node *currentLocation = [self first];
NSUInteger idx;
for(idx = 0; i < (index - 1); ++idx)
{
currentLocation = [currentLocation next];
}
Node *previousNode = currentLocation; // store a reference to the previous node
currentLocation = [currentLocation next]; // now at the point we want to insert
[previousNode setNext:newNode];
[newNode setPrevious:previousNode];
[newNode setNext:currentLocation];
[currentLocation setPrevious:newNode];
[self setCount:[self count]+1];