Java でジェネリック LinkedList を作成する
Suraj P
2023年10月12日
この記事では、Java で一般的な singly LinkedList を作成する方法を説明します。
Java での LinkedList の簡単な紹介
LinkedListsは、ランダムなアドレスのノードにデータを格納し、連続していない場所にデータを格納する線形データ構造です。
各ノードには、data と reference(アドレス) の 2つの部分があります。 Data/value フィールドには値が格納され、reference フィールドにはリンク リストの次のノードのアドレスが格納されます。
メンバー関数として実装されるこのデータ構造の一般的な操作の一部を次に示します。
addNode()- このメソッドは、LinkedListの末尾に新しい要素を追加するために使用されます。removeNode(value)- このメソッドは、指定された値を持つノードを削除します。addNode(position,value)- このメソッドは、特定の位置に値を追加するために使用されます。clear()- このメソッドはLinkedList全体をクリアします。isEmpty()- このメソッドは、LinkedListが空かどうかを確認するために使用されます。length()- このメソッドはLinkedListの長さを返します。
Java での単独の LinkedList の一般的な実装
通常の LinkedList は、整数、文字列、ブール値、浮動小数点数などの 1つのタイプの値しか格納できません。したがって、作成時にタイプを指定する必要がありますが、LinkedList を作成する場合はどうすればよいでしょうか。 あらゆるデータ型のデータを保存します。 そのために、Java の generics の概念を使用します。
ジェネリック ノード クラスの作成:
以下のコードでは、T は LinkedList に格納されているデータのタイプを示します。
class Node<T> {
T value;
Node<T> nextPtr;
Node(T value) {
this.value = value;
this.nextPtr = null;
}
}
それでは、一般的な LinkedList クラス作成メソッドを作成しましょう。
-
add()関数:void add(T value) { Node<T> temp = new Node<>(value); // creating a new node if (this.head == null) // checking if the list is empty head = temp; else // if the list is not empty, we go till the end and add the node { Node<T> tr = head; while (tr.nextPtr != null) { tr = tr.nextPtr; } tr.nextPtr = temp; } length = length + 1; // increasing the length of list } -
remove()関数:void remove(T key) { Node<T> prev = new Node<>(null); prev.nextPtr = head; Node<T> next = head.nextPtr; Node<T> tr = head; boolean isNodepresent = false; // to check if node is present if (head.value == key) { head = head.nextPtr; isNodepresent = true; } while (tr.nextPtr != null) { if (String.valueOf(tr.value).equals( String.valueOf(key))) { // if the node is present, we break the loop prev.nextPtr = next; // we assign previous node's nextPtr to next node isNodepresent = true; break; } prev = tr; // updating the previous and next pointers tr = tr.nextPtr; next = tr.nextPtr; } if (isNodepresent == false && String.valueOf(tr.value).equals(String.valueOf(key))) { prev.nextPtr = null; isNodepresent = true; } if (isNodepresent) { length--; // if the node is present, we reduce the length } else { System.out.println("The value is not present inside the LinkedList"); } } -
add(位置,値)関数:void add(int position, T value) { if (position > length + 1) // if the position entered is more than the list length { System.out.println("Position out of bound"); return; } if (position == 1) { // if the position is one we'll just Node<T> temp = head; head = new Node<T>(value); head.nextPtr = temp; return; } Node<T> tr = head; Node<T> prev = new Node<T>(null); // creating a new node prev while (position - 1 > 0) // we find the position in the list { prev = tr; tr = tr.nextPtr; position--; } prev.nextPtr = new Node<T>(value); // update the next pointer of previous node prev.nextPtr.nextPtr = tr; } -
getLength()関数:int getLength() { return this.length; // returns the length of the list } -
isEmpty()関数:boolean isEmpty() { if (head == null) // if the list is empty we return true return true; else return false; } -
clear()関数:void clear() { head = null; // make head as null and length as zero length = 0; } -
toString()関数:以下のコードでは、
LinkedListの内容を出力するためにtoStringメソッドを追加してオーバーライドしています。@Override public String toString() { Node<T> temp = head; String str = "{ "; if (temp == null) // if the list is empty { System.out.println("list is empty"); } while (temp.nextPtr != null) // we keep appending data to string till the list is empty { str += String.valueOf(temp.value) + "->"; temp = temp.nextPtr; } str += String.valueOf(temp.value); return str + "}"; // we finally return the string }
main クラスを使用した完全な作業コード:
class Node<T> {
T value;
Node<T> nextPtr;
Node(T value) {
this.value = value;
this.nextPtr = null;
}
}
class LinkedList<T>
{
Node<T> head;
private int length = 0;
LinkedList()
{
this.head = null;
}
void add(T value)
{
Node<T> temp = new Node<>(value);
if(this.head == null)
head = temp;
else
{
Node<T> tr = head;
while(tr.nextPtr!=null){
tr = tr.nextPtr;
}
tr.nextPtr = temp;
}
length = length + 1;
}
void remove(T key)
{
Node<T> prev = new Node<>(null);
prev.nextPtr = head;
Node<T> next = head.nextPtr;
Node<T> tr = head;
boolean isNodepresent = false;
if(head.value == key ){
head = head.nextPtr;
isNodepresent =true;
}
while(tr.nextPtr!=null)
{
if(String.valueOf(tr.value).equals(String.valueOf(key))){
prev.nextPtr = next;
isNodepresent = true;
break;
}
prev = tr;
tr = tr.nextPtr;
next = tr.nextPtr;
}
if(isNodepresent==false && String.valueOf(tr.value).equals(String.valueOf(key))){
prev.nextPtr = null;
isNodepresent = true;
}
if(isNodepresent)
{
length--;
}
else
{
System.out.println("The value is not present inside the LinkedList");
}
}
void add(int position,T value)
{
if(position>length+1)
{
System.out.println("Position out of bound");
return;
}
if(position==1){
Node<T> temp = head;
head = new Node<T>(value);
head.nextPtr = temp;
return;
}
Node<T> tr = head;
Node<T> prev = new Node<T>(null);
while(position-1>0)
{
prev = tr;
tr = tr.nextPtr;
position--;
}
prev.nextPtr = new Node<T>(value);
prev.nextPtr.nextPtr = tr;
}
int getLength()
{
return this.length;
}
boolean isEmpty()
{
if(head == null)
return true;
else
return false;
}
void clear()
{
head = null;
length = 0;
}
@Override
public String toString()
{
Node<T> temp = head;
String str = "{ ";
if(temp == null)
{
System.out.println( "list is empty");
}
while(temp.nextPtr!=null)
{
str += String.valueOf(temp.value) +"->";
temp = temp.nextPtr;
}
str += String.valueOf(temp.value);
return str+"}";
}
}
public class Example
{
public static void main(String[] args) {
LinkedList<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(3);
System.out.println(ll);
ll.remove(3);
System.out.println(ll);
ll.add(2,800);
System.out.println(ll);
}
}
出力：
{ 1->2->3}
{ 1->2}
{ 1->800->2}
著者： Suraj P
