标签: linked-list

取自Apache TreeListdoc:

以下相对性能统计数据表示此类:

             get  add  insert  iterate  remove
 TreeList       3    5       1       2       1
 ArrayList      1    1      40       1      40
 LinkedList  5800    1     350       2     325

Run Code Online (Sandbox Code Playgroud)

它继续说:

LinkedList很少是一个很好的实施选择.TreeList它几乎总是一个很好的替代品,虽然它确实使用了更多的内存.

我的问题是:

• 什么是与ArrayList add, insert和remove次粉碎 LinkedList？我们是否应该期望,真实世界的插入和移除案例非常有利ArrayList？

• 这TreeList简直就是钉在古老的棺材里LinkedList吗？

我很想得出结论,他们已经摊销或忽略了ArrayList成长的痛苦,并没有考虑到LinkedList已经找到的物品的插入和移除时间.

我有一个带有XmlElementWrapper注释的类,如:

...

  @XmlElementWrapper(name="myList")
    @XmlElements({
    @XmlElement(name="myElement") }
    )
    private List<SomeType> someList = new LinkedList();

...这段代码生成XML

<myList>
  <myElement> </myElement>
  <myElement> </myElement>
  <myElement> </myElement>
</myList>

到现在为止还挺好.

但是现在我需要在list标签中添加属性以获得XML

<myList number="2">
  <myElement> </myElement>
  <myElement> </myElement>
  <myElement> </myElement>
</myList>

有没有一种'聪明的方法来实现这一目标而不创建一个包含代表列表的新类？

在C#中创建循环链表的最佳方法是什么？我应该从LinkedList <T>集合中派生出来吗？我打算使用这个链接列表创建一个简单的地址簿来存储我的联系人(这将是一本糟糕的地址簿,但我不在乎因为我将是唯一一个使用它的人).我主要只想创建关键链表,以便我可以在其他项目中再次使用它.

如果您认为链接列表不是正确的方法,请告诉我哪种方式会更好.

这是微软书面测试期间提出的编程问题之一.我提出了我想出的问题和答案.事情虽然看起来很全面(至少对我来说),但我觉得可以减少行数.它在C中被问到我是一个Java人,但我设法编写它(我的答案可能包含太多类似Java的语法)

好的,这是问题所在.

您有两个已经排序的列表,您必须合并它们并返回一个没有任何新额外节点的新列表.返回的列表也应该排序.

方法签名是,

Node* MergeLists(Node* list1, Node* list2);

struct Node{
    int data;
    Node *next;
}

以下是我提出的解决方案,

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer …

我有一个链表samples:

protected LinkedList<RawDataset> samples = new LinkedList<RawDataset>();

我将元素添加到线程1中的列表中,如下所示:

this.samples.offer(data);

我正在第二个线程中从中检索元素,如下所示:

public RawDataset retrieveSample() {
    return this.samples.poll();
}

这会被认为是线程安全的吗？即使线程1和2都在修改列表,它们只在列表的头部或尾部专门执行,对吧？

如果不是,任何人都可以指向我的Java API中的类poll/ offer并且肯定是线程安全的吗？

先感谢您.

BTW:Collections.synchronizedList(new LinkedList())不会让我访问offer/ poll.

我需要按字母顺序对链表进行排序.我有一个链接列表,其中包含乘客姓名,并且需要按字母顺序对乘客姓名进行排序.怎么会这样做？有人有任何参考或视频吗？

如何释放在另一个函数中分配的节点？

struct node {
    int data;
    struct node* next;
};

struct node* buildList()
{
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;

    head = malloc(sizeof(struct node));
    second = malloc(sizeof(struct node));
    third = malloc(sizeof(struct node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    return head;
}  

我在main()中调用了buildList函数

int main()
{
    struct node* h = buildList();
    printf("The second element is %d\n", h->next->data);
    return 0;
} …

我有一个通过AbstractTableModel填充链表的Jtable.

我想要做的是当我点击(左键单击)JTable中的一行时,链表是搜索(在这种情况下它包含电影标题)并在Jtextboxes中的链表中显示值

我该怎么做呢？

这是代码

• GUI_g:http://pastebin.com/J3qtjn8J
• ProgramTableModel:http://pastebin.com/Dwkc9Cz3
• 处理:http://pastebin.com/qHnkvCbr
• 主要:http://pastebin.com/K4yGYX9H

我猜它会将所选行中的数据检索到一个数组中,将其拆分并放入jtextareas中.我怎样才能做到这一点 ？

从链表标签维基摘录:

链表是一种数据结构,其中元素包含对下一个(以及可选的前一个)元素的引用.链接列表提供在任何位置的O(1)插入和移除,O(1)列表串联,以及前(和可选后)位置的O(1)访问以及O(1)下一个元素访问.随机访问具有O(N)复杂性并且通常是未实现的.

^{(强调我的)}

我很惊讶地看到这个 - 如何在一个随机索引中插入一个复杂度低于简单读取索引的列表？

所以我查看了源代码java.util.LinkedList.该add(int, E)方法是:

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

该addBefore(E, Entry<E>方法只是指针重新分配,但也有entry(int)方法:

if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e …

我正在阅读的书,链接列表数据结构简介(演示文稿21),有2个链表的例子.这是第一个:

EnemySpaceShip* getNewEnemy ()
{
    EnemySpaceShip* p_ship = new EnemySpaceShip;
    p_ship->x_coordinate = 0;
    p_ship->y_coordinate = 0;
    p_ship->weapon_power = 20;
    p_ship->p_next_enemy = p_enemies;
    p_enemies = p_ship;
    return p_ship;
}

链接列表的第二个示例是这样的:

EnemySpaceShip* addNewEnemyToList (EnemySpaceShip* p_list)
{
    EnemySpaceShip* p_ship = new EnemySpaceShip;
    p_ship->x_coordinate = 0;
    p_ship->y_coordinate = 0;
    p_ship->weapon_power = 20;
    p_ship->p_next_enemy = p_list;
    return p_ship;
}

然后这本书写道:

请注意,此函数不同,getNewEnemy因为它返回指向列表的指针,而不是新的敌人.

我不明白的是他的意思是"第二个函数返回一个指向列表的指针"和"第一个函数返回新的敌人".我以为他们都创造了一个叫做的新敌人p_ship(既是指针又是新敌人)并将其归还.这句话是什么意思？