Вдвойне связанный список, под капотом

Question

Допустим, у вас есть 2 класса:

 - Node
 - Doubly linked list (DLL)

Ваш main создает группу узлов, которые что-то знают о себе, например, свое имя, а затем вызывает add(Node*) метод DLL.

Чтобы отслеживать эти Node указатели, (я бы подумал) DLL должен поддерживать их массив. Есть ли способ избежать этого?(или любая другая структура данных в этом отношении)

Как DLL реализован под капотом?Использует ли он массивы или что-то еще?

Answer 1

Если бы вы использовали массив, вы бы избавились от всех преимуществ производительности при использовании списков. Под капотом связанный список содержит значение «Узла» и указатели на следующий и предыдущий Узлы. Увеличение / уменьшение итератора позволяет получить доступ к следующим / предыдущим указателям узлов.

Answer 2

Есть способ избежать этого. На самом деле вам вообще не нужно отслеживать все указатели в одном месте, потому что сами Node являются структурой данных.

РЕДАКТИРОВАТЬ: Только что увидел ваш комментарий 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

Нет, нет массивов. Использование массива, как правило, нарушает гарантии производительности связанного списка. Нет необходимости отслеживать все указатели; каждый узел содержит указатели на другие узлы, и пока ваша программа удерживает указатель только на один узел где-то в списке, никакие узлы не будут потеряны, потому что с этого можно добраться до каждого другого узла.