1

2つのクラスがあるとしましょう:

 - Node
 - Doubly linked list (DLL)

は、たとえば名前など、自分main自身について何かを知っているノードの束を作成し、のadd(Node*)メソッドを呼び出しますDLL

これらのポインタを追跡するためにNode、(私は思うに)DLLそれらの配列を維持する必要があります。それを回避する方法はありますか?(またはその他のデータ構造)

内部でどのようにDLL実装されていますか?配列などを使用していますか?

4

4 に答える 4

2

いいえ、アレイはありません。一般に、配列を使用すると、リンクリストのパフォーマンス保証が損なわれます。すべてのポインタを追跡する必要はありません。各ノードには他のノードへのポインタが含まれ、プログラムがリスト内の1つのノードへのポインタを保持している限り、そのノードから他のすべてのノードに到達できるため、ノードが失われることはありません。

于 2011-09-16T03:59:41.313 に答える
2

配列を使用すると、リストを使用することによるパフォーマンス上の利点がすべてなくなります。内部では、リンクされたリストに「ノード」の値と、次および前のノードへのポインタが含まれています。イテレータのインクリメント/デクリメントは、ノードの次/前のポインタにアクセスします。

于 2012-10-21T21:24:14.977 に答える
2

それを回避する方法があります。実際には、すべてのポインターを 1 つの場所で追跡する必要はまったくありません。これは、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;

それだけです。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];
于 2011-09-16T04:01:00.320 に答える
2

このリンクは、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
于 2011-09-16T04:03:26.463 に答える