Javaでリンクリストを逆にする
1. 序章
このチュートリアルでは、Javaに2つのリンクリスト反転アルゴリズムを実装します。
2. リンクリストのデータ構造
リンクリストは、各要素のポインタが順序を決定する線形データ構造です。 リンクリストの各要素には、リストデータを格納するデータフィールドと、シーケンス内の次の要素を指すポインタフィールドが含まれます。また、headポインタを使用してリンクリストの開始要素をポイントします。
リンクリストを逆にした後、 head は元のリンクリストの最後の要素を指し、各要素のポインターは元のリンクリストの前の要素を指します。
Javaには、ListおよびDequeインターフェースの二重リンクリスト実装を提供するLinkedListクラスがあります。 ただし、このチュートリアルでは、一般的な単一リンクリストのデータ構造を使用します。
まず、リンクリストの要素を表すListNodeクラスから始めましょう。
public class ListNode {
private int data;
private ListNode next;
ListNode(int data) {
this.data = data;
this.next = null;
}
// standard getters and setters
}
ListNodeクラスには2つのフィールドがあります。
- 要素のデータを表す整数値
- 次の要素へのポインタ/参照
リンクリストには、複数のListNodeオブジェクトが含まれる場合があります。 たとえば、ループを使用して上記のサンプルリンクリストを作成できます。
ListNode constructLinkedList() {
ListNode head = null;
ListNode tail = null;
for (int i = 1; i <= 5; i++) {
ListNode node = new ListNode(i);
if (head == null) {
head = node;
} else {
tail.setNext(node);
}
tail = node;
}
return head;
}
3. 反復アルゴリズムの実装
Javaに反復アルゴリズムを実装しましょう。
ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
while (current != null) {
ListNode nextElement = current.getNext();
current.setNext(previous);
previous = current;
current = nextElement;
}
return previous;
}
この反復アルゴリズムでは、2つの ListNode 変数、previousおよびcurrentを使用して、リンクリスト内の2つの隣接する要素を表します。 反復ごとに、これら2つの要素を逆にしてから、次の2つの要素にシフトします。
最終的に、現在のポインターは null、になり、前のポインターは古いリンクリストの最後の要素になります。 したがって、前のは、逆リンクリストの新しいヘッドポインターでもあり、メソッドから返します。
この反復的な実装は、簡単な単体テストで検証できます。
@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseList(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}
この単体テストでは、最初に5つのノードを持つサンプルのリンクリストを作成します。 また、リンクリストの各ノードに正しいデータ値が含まれていることを確認します。 次に、反復関数を呼び出してリンクリストを逆にします。 最後に、逆リンクリストをチェックして、データが期待どおりに逆になっていることを確認します。
4. 再帰的アルゴリズムの実装
それでは、再帰アルゴリズムをJavaに実装しましょう。
ListNode reverseListRecursive(ListNode head) {
if (head == null) {
return null;
}
if (head.getNext() == null) {
return head;
}
ListNode node = reverseListRecursive(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return node;
}
reverseListRecursive 関数では、最後の要素に到達するまで、リンクリストの各要素に再帰的にアクセスします。 この最後の要素は、逆リンクリストの新しいヘッドになります。 また、部分的に反転されたリンクリストの最後にvisited要素を追加します。
同様に、この再帰的な実装を簡単な単体テストで検証できます。
@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseListRecursive(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}
5. 結論
このチュートリアルでは、リンクリストを逆にするために2つのアルゴリズムを実装しました。 いつものように、記事のソースコードはGitHubでから入手できます。