LinkedListの実装とソート

今回は配列操作時に空間計算量を大幅に落とせるLinkedListを実装していきます。ArrayListと違い、ランダムアクセスが不可能なため要素の呼び出しにはO(n)の時間を要するところが難点ですが、要素の追加や削除はノードを繋ぎ変えるだけで済みます。

Nodeクラスの実装

LinkedListのノードとなる部分を実装します。

ノードに割り当てる要素の型予測をしなくてよいようにジェネリクスを使用します。

public class Node<T extends Comparable<T>> {

    private T data;
    private Node<T> next;
  
    public Node(T data) {
      this.data = data;
      this.next = null;
    }
  
    public Node(T data, Node<T> next) {
      this.data = data;
      this.next = next;
    }
  
    public T getData() {
      return data;
    }
  
    public void setData(T data) {
      this.data = data;
    }
  
    public Node<T> getNext() {
      return next;
    }
  
    public void setNext(Node<T> next) {
      this.next = next;
    }
  }

LinkedListクラスの実装

public class ListNode<T extends Comparable<T>> {
　　　　Node head;
...
}

コンストラクタ

今回はインスタンス化と同時に先頭のノードを生成します。

public ListNode(Node data){
        this.head = data;
    }

追加メソッド

データ追加の際、次のノードを指定するためのポインタを生成しておきます。

 public void append(T data){
        Node currNode = head;
        while (currNode.getNext() != null){
            currNode = currNode.getNext();
        }currNode.setNext(new Node((Comparable) data));
        System.out.println(data + " is added");
        return;
    }

ノードの再接続

結局これは要素の削除と同じことになりますが、パラメータが次のノードのデータと一致した時にノードを繋ぎ変えるメソッドを作成します。

public void pop(T target){

        Node currNode = head;
        while(currNode.getNext() != null){

            if (currNode.getNext().getData() == target){
                Comparable n1 = currNode.getNext().getNext().getData();
                currNode.getNext().setData(n1);
                currNode.setNext(currNode.getNext().getNext());
                System.out.println(target + " is popped.");
            }currNode = currNode.getNext();
        }
    }

toString()

リストを可視化するためのメソッドを作っておきます。

public String toString(){
        String result = "|HEAD| - |";
        Node curNode = head;
        while(curNode != null){
            result += curNode.getData() + "| - |";
            curNode = curNode.getNext();
        }
        return result + "TAIL|";
    }

ソートメソッド

要素を昇順に並べ替えるアルゴリズムを適用します。

今回はバブルソートを使用します。

public void sort(){
        Node currNode = head;
        boolean isSwapped = true;
        while(isSwapped){
            isSwapped = false;
            while (currNode.getNext() != null){
            Comparable n1 = currNode.getData();
            Comparable n2 = currNode.getNext().getData();
        
            if (n1.compareTo(n2) > 0){
                currNode.setData(n2);;
                currNode.getNext().setData(n1);
                System.out.println(n1 + "->" + n2);
                isSwapped = true;
            }
            currNode = currNode.getNext();
            }
            currNode = head;
        }
    }

ノードの再接続をisSwappedがTrueの間ひたすら繰り返していきます。この時、空間計算量はほとんど変わりません。

挿入メソッド

指定のインデックスにパラーメータから受け取ったデータを格納したノードを挿入するメソッドを実装します。インデックス箇所までノードを辿っていき、たどり着いたら一旦次ノードとの接続を解除して新しいノードを接続し直すイメージです。

public void insert(T data,int index){
        Node currNode = head;
        for (int i = 1; i < index; i++){
            currNode = currNode.getNext();
        }
        Node n1 = currNode.getNext();
        currNode.setNext(new Node((Comparable) data));
        currNode = currNode.getNext();
        currNode.setNext(n1);
        while (currNode.getNext() != null){
            currNode = currNode.getNext();
            }
        }

メインメソッド

ソートを実行してみます。

public static void main(String[] args) {
        ListNode listnode = new ListNode(new Node((Comparable) new Random().nextInt(100)));
        for (int i = 0;i<2000;i++){
            listnode.append(new Random().nextInt(10000));
        }
        System.out.println(listnode);
        listnode.sort();
        System.out.println(listnode);
    }