java - java中如何构建和遍历链表数组？

Question

我编写了一个用于插入元素的链接列表，其中每个元素都有两个数据值。现在我想要的是制作锯齿状数组。这意味着我想要一个一维数组，其中每个元素都是项目的链接列表。是否真的可以将下面的单个链表变成链表数组，即 L[0]，L[1] 等，每个链表都是类似链表的开头。那么我应该在下面给出的代码中修改什么，以便我可以形成并遍历并打印值。

// Java Program to insert in a sorted list
class LinkedList1
{
Node head;  // head of list

/* Linked list Node*/
class Node
{
    int s;
    int a;
    Node next;
    Node(int starting_time,int arrival_time) {s = starting_time; a=arrival_time;next = null; }
}

/* function to insert a new_node in a list. */
void sortedInsert(Node new_node)
{
     Node current;

     /* Special case for head node */
     if (head == null || head.a >= new_node.a)
     {
        new_node.next = head;
        head = new_node;
     }
     else {

        /* Locate the node before point of insertion. */
        current = head;

        while (current.next != null &&
               current.next.a < new_node.a)
              current = current.next;

        new_node.next = current.next;
        current.next = new_node;
     }
 }

              /*Utility functions*/

/* Function to create a node */
Node newNode(int s,int a)
{
   Node x = new Node(s,a);
   return x;
}

 /* Function to print linked list */
 void printList()
 {
     Node temp = head;
     while (temp != null)
     {
        System.out.print("["+temp.s+","+temp.a+"] ");
        temp = temp.next;
     }
 }

 /* Drier function to test above methods */
 public static void main(String args[])
 {
     LinkedList1 llist = new LinkedList1();
     Node new_node;
     new_node = llist.newNode(5,6);
     llist.sortedInsert(new_node);
     new_node = llist.newNode(10,2);
     llist.sortedInsert(new_node);
     new_node = llist.newNode(7,3);
     llist.sortedInsert(new_node);
     new_node = llist.newNode(3,4);
     llist.sortedInsert(new_node);
     new_node = llist.newNode(1,5);
     llist.sortedInsert(new_node);
     new_node = llist.newNode(9,1);
     llist.sortedInsert(new_node);
     System.out.println("Created Linked List");
     llist.printList();
 }
}

Answer 1

我已将 LinkedList1 类包装在 LinkedListArray 中，并创建了几个构造函数以及一个 get 和 insert 方法。同样，您可以根据需要编写其他方法。希望这能让事情变得清楚。

public class LinkedListArray{

    private int DEFAULT_CAPACITY=10;
    private int SIZE=0;

    private LinkedList1[] arr;

    public LinkedListArray() {

        arr=new LinkedList1[DEFAULT_CAPACITY];

    }   

    public LinkedListArray(int capacity) {

        arr=new LinkedList1[capacity];

    }

    public LinkedList1 insert(int index, LinkedListArray.LinkedList1.Node Node) {

        if(arr[index]==null)    arr[index]=new LinkedList1();

        arr[index].sortedInsert(Node);;
        SIZE++;
        return arr[index];
    }

    public LinkedList1 get(int index) {

        return arr[index];
    }

    public int size() {

        return SIZE;
    }


//Java Program to insert in a sorted list
class LinkedList1
{

public LinkedList1() {} 
Node head;  // head of list

/* Linked list Node*/
class Node
{
 int s;
 int a;
 Node next;
 Node(int starting_time,int arrival_time) {s = starting_time; a=arrival_time;next = null; }
}

/* function to insert a new_node in a list. */
void sortedInsert(Node new_node)
{
  Node current;

  /* Special case for head node */
  if (head == null || head.a >= new_node.a)
  {
     new_node.next = head;
     head = new_node;
  }
  else {

     /* Locate the node before point of insertion. */
     current = head;

     while (current.next != null &&
            current.next.a < new_node.a)
           current = current.next;

     new_node.next = current.next;
     current.next = new_node;
  }
}

           /*Utility functions*/

/* Function to create a node */
Node newNode(int s,int a)
{
Node x = new Node(s,a);
return x;
}

/* Function to print linked list */
void printList()
{
  Node temp = head;
  while (temp != null)
  {
     System.out.print("["+temp.s+","+temp.a+"] ");
     temp = temp.next;
  }
}

/* Drier function to test above methods */

}


public static void main(String args[])
{
    LinkedListArray arr=new LinkedListArray();


  arr.insert(0,  new LinkedListArray().new LinkedList1().newNode(5, 4));
  arr.insert(0,  new LinkedListArray().new LinkedList1().newNode(10, 4));
  arr.insert(0, new LinkedListArray().new LinkedList1().newNode(4, 34));


  System.out.println("Created Linked List and inserted in array");
  arr.get(0).printList();
}
}