在 java 中使用双向链表制作移动光标

Question

我正在尝试为 java 中的简单移动光标编写代码。我必须使用双向链表。我也应该自己实现 doubyLinkedList class 。在这个程序中，我们首先从用户那里获取一个整数，如 n 作为行数。然后我们获取 n 行输入。每行只包含一个字符，可以是 < 或 > 或 - 或小写英文字母之一。对于 > 或 <，我们将光标向右或向左移动。对于 - 我们删除光标所在位置的字符。对于字母表，我们将它们添加到双向链表中。最后我们将结果打印在一行中，没有空格。我制作了 doubyLinkedList class 和所需的方法。我认为它工作正常，但代码的时间复杂度必须是 O(n)。我猜现在是 O(n^2)。

import java.util.*;
public class DoublyLinkedList {
static Node head = null;
static int size = 0;
class Node {
    String data;
    Node prev;
    Node next;
    Node(String d) {
        data = d;
    }
}
static Node deleteNode(Node del) {
    if (head == null || del == null)
        return null;
    if (head == del)
        head = del.next;
    if (del.next != null)
        del.next.prev = del.prev;
    if (del.prev != null)
        del.prev.next = del.next;
    del = null;
    size --;
    return head;
}
public String GetNth(int index) {
    Node current = head;
    int count = 0;
    while (current != null)
    { if (count == index)
        return current.data;
        count++;
        current = current.next;
    }
    assert (false);
    return null;
}
public static void deleteNodeAtGivenPos(int n) {
    size--;
    if (head == null || n <= 0)
        return;
    Node current = head;
    int i;
    for (i = 1; current != null && i < n; i++)
        current = current.next;
    if (current == null)
        return;
    deleteNode(current);
}
void insertFirst (String data){
    size++;
    Node newNode = new Node(data);
    if (head == null) {
        newNode.prev = null;
        head = newNode;
        return;
    }
    else
        head.prev= newNode;
    newNode.next=head;
    head = newNode;
}
void append(String data) {
    size++;
    Node newNode = new Node(data);
    Node last = head;
    newNode.next = null;
    if (head == null) {
        newNode.prev = null;
        head = newNode;
        return;
    }
    while (last.next != null)
        last = last.next;
    last.next = newNode;
    newNode.prev = last;
}
public void insertAtGivenPos(String s , int index){
    Node newNode= new Node(s);
    Node current= head;
    if (index==0)
        insertFirst(s);
    else if(index==size)
        append(s);
    else{
        for(int j = 0; j < index && current.next != null; j++){
            current = current.next;
        }
        newNode.next = current;
        current.prev.next = newNode;
        newNode.prev = current.prev;
        current.prev = newNode;
        size++;
    }
}
public void print(Node node) {
    while (node != null) {
        System.out.print(node.data + "");
        node = node.next;
    }
}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.nextLine());
    String [] arr= new String[n];
    for (int i=0; i< n; i++)
        arr[i] = sc.nextLine();
    DoublyLinkedList dll = new DoublyLinkedList();
    int cursor= 0;
    for (int i=0; i< n; i++){
        if (arr[i].matches("[a-z]")){
            dll.insertAtGivenPos(arr[i], cursor);
            cursor++;
        }
        else if (arr[i].contains("-")&& dll.GetNth(cursor-1)!= null) {
            dll.deleteNodeAtGivenPos(cursor);
            cursor--;
        }
        else if (arr[i].contains("<") && dll.GetNth(cursor-1)!= null)
            cursor--;
        else if (arr[i].contains(">") && dll.GetNth(cursor+1)!= null)
            cursor++;
    }
    dll.print(dll.head);
}
}

如何改进我的代码以降低时间复杂度？

编辑：我也明白我的代码在某些情况下给出了错误的答案。你能帮我调试一下吗？

Answer 1

您不需要内部 for 循环。接受输入后立即处理。

for (int i=0; i< n; i++)
    arr[i] = sc.nextLine();
    DoublyLinkedList dll = new DoublyLinkedList();
    int cursor= 0;
    if (arr[i].matches("[a-z]")){
        dll.insertAtGivenPos(arr[i], cursor);
        cursor++;
    }
    else if (arr[i].contains("-")&& dll.GetNth(cursor-1)!= null) {
        dll.deleteNodeAtGivenPos(cursor);
        cursor--;
    }
    else if (arr[i].contains("<") && dll.GetNth(cursor-1)!= null)
        cursor--;
    else if (arr[i].contains(">") && dll.GetNth(cursor+1)!= null)
        cursor++;
}

Answer 2

如果您不是被迫遵循实施细节，我建议不要使用游标。相反，保留一个变量 currentNode 这是 cursor 将指向的节点。因此，对于输入循环中的每个命令（或数据），您都有一个如下所示的 O(1) 操作，因此将获得 O(n) 时间复杂度。

1 - for > : change the currentNode to currentNode.next

2 - for < do the reverse

3 - for - change the previous and the next node of currentNode to point to each other (so the current is deleted)

4 - and finally for insertion : create a node and like 3, change the the side nodes to point to it

在 java 中使用双向链表制作移动光标

Make a moving cursor using doubly linked list in java

java

time-complexity

data-structures

doubly-linked-list