如何创建我自己的单链表

我想将与ArrayLists一起工作的代码转换为适用于单链表的代码。数组列表由先前创建的Shape对象组成，我知道工作。然后，可以将新形状添加到数组列表的末尾。此外，可以使用索引引用从此列表中删除特定形状。但是，当我将它切换到链表时，我并没有达到我所需要的。下面是数组列表代码：如何创建我自己的单链表

import java.util.ArrayList; 

public class ShapeLinkedList { 
    ArrayList<Shape> list = new ArrayList<Shape>(); 

    public ShapeLinkedList() { 
    } 

    public void addToRear(Shape shape) { 
     list.add(shape); 
     System.out.println("Added "+shape); 
    } 

    public Shape get(int index) { 
     return list.get(index); 
    } 

    public int size() { 
     return list.size(); 
    } 

    public Shape remove(int index) { 
     Shape temp = list.remove(index); 
     System.out.println("Removed "+temp); 
     return temp; 
    } 
}

我不能改变的方法的名称，我必须全部使用相同的方法。所以这是我到目前为止的链表：

public class ShapeLinkedList { 
    ShapeNode head; 
    int count = 0; 

    public ShapeLinkedList() {} 

    public void addToRear(Shape shape) { 
     ShapeNode end = new ShapeNode(shape); 
     if (head == null) { 
      head = end; 
     } 
     //loop through Linked List until we find the end of the list 
     while (head.next != null) { 
      head = head.next; 
      count++; 
     } 
     //set the new node to the Shape shape and the next one will be null 
     head.next = end; 
     count++; 
     //System.out.println("Added " + shape); 
    } 

    public Shape get(int index) { 
     for (int i = 0; i <= index; i++) { 

     } 
     Shape rem = ; 
     return rem 
    } 

    public int size() { 
     return count; 
    } 

    public Shape remove(int index) { 
     if (index == 0) { 
      Shape temp = head; 
      head = head.next; 
     } else if() { 
      Shape temp = ; 
     } 
     //System.out.println("Removed " + temp); 
     return temp; 
    } 

    private class ShapeNode { 
     Shape shp; 
     ShapeNode next; 

     public ShapeNode(Shape shp) { 
      this.shp = shp; 
      next = null; 
     } 
    } 
}

我需要帮助构建吸气的形状，因为我不知道如何找到链表的索引，我不知道如何引用该索引处的特定形状类型。另外，我需要使用remove方法的帮助。我觉得有一次我得到了我遇到的第一个吸气剂的必要信息，我应该能够解决我的第二个问题。有没有人有有用的建议？

来源

2012-12-02 user1850008

看看现有的'LinkedList'源代码。 http://www.docjar.com/html/api/java/util/LinkedList.java.html –

谢谢。这有助于我的一个问题。你能否就另一个问题给我提供建议？我需要找到位于索引位置的Shape对象，但我所知道的就是ShapeNode。我将如何获得那里的形状？ – user1850008

为什么，为什么为什么？与LinkedList相比，ArrayList几乎总是更快，内存更有效。特别是如果您需要通过索引访问元素（ArrayList中的O（1）和LinkedList中的O（N））。即使你真的想要一个链表，为什么不使用标准的，经过充分测试的java.util.LinkedList而不是你自己的实现呢？ –

public Shape get(int index) { 
     ShapeNode temp = head; 
     while(index-- > 0) { 
      temp = temp.next; 
     } 
     if(temp == null) 
      throw new IndexOutOfBoundsException("Invalid index : " + index); 
     Shape rem = temp.shp; 
     return rem; 
    }

但是这是O(n)被linkedList。

来源

2012-12-04 13:52:15 sundar

如何创建我自己的单链表

回答

相关问题