Итак, я создаю связанный список без использования встроенного.У меня есть куча методов для моего задания, которые мне нужны для работы.У меня все работает до удаления элементов из LL.Мне не нужен (хотя и не против) полностью функционирующий метод, мне просто нужно знать, каковы будут мои шаги.Вот мой код:
public class MoveToFrontList {
private StringCountElement head; // the head reference
private StringCountElement tail; // the tail reference
private int size; // the size of the list (number of valid items)
/**
* _Part 1: Implement this constructor._
*
* Creates a new, initially empty MoveToFontList. This list should be a
* linked data structure.
*/
public MoveToFrontList() {
head = new StringCountElement(); //allocating memory for head
tail = head; //replicating head onto tail
//head.next = tail; //making pointer of next from head to tail
//tail.prev = head; //making pointer of prev from tail to head
}
/**
* This method increments the count associated with the specified string
* key. If no corresponding key currently exists in the list, a new list
* element is created for that key with the count of 1. When this method
* returns, the key will have rank 0 (i.e., the list element associated with
* the key will be at the front of the list)
*
* @param key
* the string whose count should be incremented
* @return the new count associated with the key
*/
public int incrementCount(String key) {
StringCountElement s = find(key);
if (s != null) {
// found the key, splice it out and increment the count
spliceOut(s);
s.count++;
} else {
// need to create a new element
s = new StringCountElement();
s.key = key;
s.count = 1;
}
// move it to the front
spliceIn(s, 0);
return s.count;
}
/**
*
* @return the number of items in the list
*/
public int size() {
return size;
}
/**
* _Part 2: Implement this method._
*
* Find the list element associated with the specified string. That is, find
* the StringCountElement that a key equal to the one specified
*
* @param key
* the key to look for
* @return a StringCountElement in the list with the specified key or null
* if no such element exists.
*/
public StringCountElement find(String key) {
StringCountElement temp = head; //creating a temp object to evaluate
for(int i = 0; i <= size(); i++){
if(temp.key == null){
return null;
}
if(temp.key.equals(key)){
return temp;
}
if(temp.next != null) {
temp = temp.next;
}
}
return null; //returning null since no object with the right key was found
}
/**
* _Part 3: Implement this method._
*
* Compute the rank of the specified key. Rank is similar to position, so
* the first element in the list will have rank 0, the second element will
* have rank 1 and so on. However, an item that does not exist in the list
* also has a well defined rank, which is equal to the size of the list. So,
* the rank of any item in an empty list is 0.
*
* @param key
* the key to look for
* @return the rank of that item in the rank 0...size() inclusive.
*/
public int rank(String key) {
int rank = 0;
StringCountElement temp = head;
do{
if(temp.key == null){
return size();
}
if(temp.key.equals(key)) {
return rank;
}
if(temp.next != null) {
temp = temp.next;
}
rank++;
} while(temp.next != null);
return size();
}
/**
* _Part 4: Implement this method._
*
* Splice an element into the list at a position such that it will obtain
* the desired rank. The element should either be new, or have been spliced
* out of the list prior to being spliced in. That is, it should be the case
* that: s.next == null && s.prev == null
*
* @param s
* the element to be spliced in to the list
* @param desiredRank
* the desired rank of the element
*/
public void spliceIn(StringCountElement s, int desiredRank) {
StringCountElement temp = head;
for(int i=0; i < desiredRank; i++){ //reaching desired rank location
temp = temp.next;
}
if(desiredRank == 0){
head = s;
size++;
return;
}
//temp will be the spot that s will take over
s.next = temp; // pointing element after s to temp
s.prev = temp.prev; // pointing previous element before s to be previous element before temp
temp.prev.next = s; // pointing element before temp to s element
temp.prev = s; // pointing previous element before temp to be s
size++;
return;
}
/**
* _Part 5: Implement this method._
*
* Splice an element out of the list. When the element is spliced out, its
* next and prev references should be set to null so that it can safely be
* splicedIn later. Splicing an element out of the list should simply remove
* that element while maintaining the integrity of the list.
*
* @param s
* the element to be spliced out of the list
*/
public void spliceOut(StringCountElement s) {
return;
}
}
Так что мне нужна помощь с частью 5. Вещи, которые я знаю до сих пор, мне понадобятся контрольные примеры для первого и последнего элемента в LL.Также я думаю, что это назначение требует, чтобы голова и хвост использовались, а не как пустые ссылки.
Я также знаю, что метод splicein также нуждается в тестовом примере для последнего элемента.Кроме того, есть ли рекомендации по упрощению и / или очистке моего кода?Любая помощь приветствуется!Спасибо!
РЕДАКТИРОВАТЬ: Вот что содержит элемент:
/**
* A Container class for a doubly linked data structure that
* stores String keys and associated integer counts.
*/
public class StringCountElement {
public StringCountElement next;
public StringCountElement prev;
public String key;
public int count;
}