在 LinkedList 中按索引搜索

Question

我创建了自己的链表，其中包含一首歌曲 object（标题、艺术家等）。我正在尝试添加一个功能，用户可以在其中输入索引位置，并且有关歌曲的信息会显示在该特定索引处。我无法获取索引的位置。目前我每次运行这个它都找不到索引处的信息。我不确定是否需要实现搜索功能，或者我只是搜索错误。

我目前是如何尝试按索引搜索的

System.out.print("Enter song index location: ");
int searchIndex = input.nextInt();
for (int i = 0; i < list.size(); i++){
    if ( list.get(i).getValue().equals(searchIndex) ){
            System.out.println(list.get(i).getValue());
            found = true;
    }
}
if ( found != true ){
    System.out.println("Song does not exist.");
}

这是我的链表class

public class LinkedList {
private Node first;
private Node last;
public LinkedList(){
    first = null;
    last = null;
}
public boolean isEmpty(){
    return first == null;
}
public int size(){
    int count = 0;
    Node p = first;
    while( p != null ){
        count++;
        p = p.getNext();
    }
    return count;
}
public Node get( int i ){
    Node prev = first;
    for(int j=1; j<=i; j++){
        prev = prev.getNext();
}
    return prev;
}
public String toString(){
    String str = "";
    Node n = first;
    while( n != null ){
        str = str + n.getValue() + " ";
         n = n.getNext();
    }
    return str;
}
public void add( Song c ){
    if( isEmpty() ) {
        first = new Node(c);
        last = first;
    }else{
        Node n = new Node(c);
        last.setNext(n);
        last = n;
    }
}

节点Class

public class Node {
private Song song;
private Node next;
public Node( Song s ){
    song = s;
    next = null;
}
public Node( Song s, Node n ){
    song = s;
    next = n;
}
public Node getNext(){
    return next;
}
public void setNext(Node n){
    next = n;
}
public Song getValue(){
    return song;
}
public void setValue( Song s ){
    song = s;
}

Answer 1

看起来更像是Song的线性搜索。您正在检查输入的值（一个 int，searchIndex）是否与 Nody.getValue() 匹配，returns 一首歌曲。

如果您尝试通过索引获取，似乎您只需调用 LinkedList.get(searchIndex)?

此外：

应该没有理由存储最后一个节点，因为您没有双向链表（您可以从任一端导航）。你只需要第一个节点，然后你使用 Node.next() 导航。
通过在调用 add() 时递增它并在调用 remove() 时递减它来维护计数可能会更高效。

您或许应该对 get() 方法进行边界检查：

public Node get(int i) {
    if (i >= size()) {
        throw new IndexOutOfRangeException();
    }
    Node n = first;
    int j = 0;
    while (i != j) {
        n = n.getNext();
    }
    return n;
}

建立编码风格并坚持下去！有时参数周围有 spaces，有时则没有。有时 space 在左大括号之前，有时则不需要。以上就是我的做法

Answer 2

在链表中，您必须遍历整个列表（遍历当前节点）才能找到对象。

您的搜索应该类似于：

if (list.isEmpty()){
    System.out.println("Song does not exist.");
}

boolean found = false;
int searchIndex = input.nextInt();

Node current = list;
    while(current != null){
        if(current.equals(searchIndex)){
        found = true; //found song
        break;
        }
    current = current.next;
    }
return current;
}

Answer 3

考虑到您 LinkedList:

中的功能，您似乎只需要这样做

System.out.print("Enter song index location: ");
int searchIndex = input.nextInt();
if (searchIndex >= 0 && searchIndex < list.size(){ 
   System.out.println(list.get(searchIndex).getValue());
}
else{
    System.out.println("Song does not exist.");
}

在 LinkedList 中按索引搜索

Searching by Index in a LinkedList

java

linked-list