doubly-linked-list - 双向链表，在引擎盖下

Question

假设您有 2 个课程：

 - Node
 - Doubly linked list (DLL)

你main创建了一堆节点，他们对自己有所了解，例如他们的名字，然后add(Node*)调用DLL.

为了跟踪这些Node指针，（我认为）DLL应该维护它们的数组。有没有办法避免它？（或与此相关的任何其他数据结构）

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

Answer 1

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

Answer 2

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

编辑：刚刚看到你的 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;

这就是你所需要的。插入或删除节点涉及指针洗牌和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];

Answer 3

此链接提供了 Obj-C 中双向链表的实现。通常，您不使用数组，因为不需要跟踪所有指针。

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

Answer 4

如果您使用数组，您将摆脱使用列表的所有性能优势。在引擎盖下，链表包含“节点”的值和指向下一个和前一个节点的指针。迭代器递增/递减访问节点的下一个/上一个指针。