双链接列表，在引擎盖下面

Question

假设您有两个类：

 - Node
 - Doubly linked list (DLL)

您的main创建了一组节点，这些节点了解自己的一些情况，比如它们的名称，然后调用DLL的add(Node*)方法。

为了跟踪这些Node指针，DLL应该维护它们的数组。有办法避免吗？(或任何其他数据结构)

DLL是如何在引擎盖下实现的？它是使用数组还是其他什么的？

Answer 1

有个办法可以避免它。实际上，您根本不需要跟踪同一位置上的所有指针，因为Node本身就是数据结构。

编辑:刚看到你的目标-C评论。

Node应该有(Objective语法)：

// 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;

这就是你所需要的。插入或删除节点涉及指针洗牌和count调整，访问是从两端顺序进行的。

add:(Node*)newNode的字面意思是：

[newNode setPrevious:[self last]];
[[self last] setNext:newNode];
[self setLast:newNode];
[self setCount:[self count]+1];

..whereas 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];

Answer 2

不没有数组。一般来说，使用数组会破坏链接列表的性能保证。不需要跟踪所有的指针；每个节点都包含指向其他节点的指针，只要您的程序在列表中的某个位置保留一个指向某个节点的指针，任何节点都不会丢失，因为可以从该节点到达每个其他节点。

Answer 3

这个链接在Obj中提供了一个双链接列表的实现。通常，您不使用数组，因为不需要跟踪所有的指针。

//
//  LinkedList.h
//

// Structure representing a 
// doubly-linked list node.
typedef struct ListNode ListNode;
struct ListNode {
    int value;
    ListNode *next;
    ListNode *prev;
};


@interface LinkedList : NSObject {
@private 
    ListNode *head;
    ListNode *iterator;
    //bool reachedHead;
    //bool reachedTail;
}   

- (id)initWithHead: (int)value;
- (void)addToFront: (int)value;
- (int)getFirst;
- (int)getCurrent;
- (int)getNext;
- (int)getPrevious;

- (bool)atHead;
- (bool)atTail;

- (int)removeCurrent;

@end

执行情况：

//
//  LinkedList.m
//

#import "LinkedList.h"


@implementation LinkedList


/* Instantiates new linked list with a 
 * given first element. 
 */
- (id)initWithHead: (int)value 
{
    ListNode *n;
    self = [super init];
    if (self) {
        // creating head node with given value
        n = (ListNode *)malloc(sizeof(ListNode));
        n->value = value;
        n->next = NULL;
        n->prev = NULL;
        head = n;
        // initializing iterator to default
        [self getFirst];
    }
    return self;    
}


/* Adds a new element to the
 * front of the list */
- (void)addToFront: (int)value
{
    ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    n->value = value;
    n->next = head;
    n->prev = NULL;
    // new element becomes the head node
    head->prev = n;
    head = n;
}


/* Sets internal iterator to
 * the head node and returns its
 * value */
- (int)getFirst {
    iterator = head;
    //reachedHead = TRUE;
    //reachedTail = FALSE;
    return (head->value);
}

/* Returns the value of the iterator node
 */
- (int)getCurrent {
    return (iterator->value);
}


/* Iterates to the next node in order and
 * returns its value */
/*
- (int)getNext
{
    // if we are finished iterating,
    // set the end-of-list flag
    if (iterator->next == NULL) {
        reachedTail = TRUE;
    } else {
        // if we're leaving the head
        // node, set the flag
        if (iterator->prev == NULL) {
            reachedHead = FALSE;
        }
        iterator = iterator->next;
    }
    return (iterator->value);
}
*/
- (int)getNext
{
     if (iterator->next != NULL) {
          iterator = iterator->next;
     }
     return (iterator->value);
}


/* Iterates to the previous node in 
 * order and returns its value */
/*
- (int)getPrevious
{
    if (iterator->prev == NULL) {
        reachedHead = TRUE;
    } else {
        if (iterator->next == NULL) {
            reachedTail = FALSE;
        }
        iterator = iterator->prev;
    }
    return (iterator->value);
}
*/
- (int)getPrevious
{
     if (iterator->prev != NULL) {
          iterator = iterator->prev;
     }
     return (iterator->value);
}


/* Indicates that iterator
 * is at the first (head) node */
- (bool)atHead 
{
    //return reachedHead;
     return (iterator->prev == NULL);
}


/* Indicates that iterator
 * is at the last (tail) node */
- (bool)atTail 
{
    //return reachedTail;
     return (iterator->next == NULL);
}


/* Removes the iterator node from
 * the list and advances iterator to the
 * next element. If there's no next element,
 * then it backs iterator up to the previous
 * element. Returns the old iterator value */
- (int)removeCurrent 
{
    int i = iterator->value;
    ListNode *l;
    // if we have only 1 item in the list...
    if ((iterator->next == NULL) && (iterator->prev == NULL)) {
        //... then we can safely delete it and set head to null
        free(iterator);
        iterator = NULL;
        head = NULL;
    } else {
        // sawing the gap between nodes
        l = iterator;
        if (iterator->next != NULL) {
            iterator->next->prev = iterator->prev;
        }
        if (iterator->prev != NULL) {
            iterator->prev->next = iterator->next;
        }
        // finally setting new iterator
        iterator = (iterator->next != NULL) ? iterator->next : iterator->prev;
        free(l);
    }
    // returning old value
    return i;
}

@end