Java データ構造

連結リストの実装 Java

2017/07/27

連結リスト

データ構造の一つである連結リストの実装をJavaで行う。

連結リストとは？

Javaでは、標準パッケージでLinkedListクラスで実装されている。
連結リストとは、連続した要素がポインタでつながれている。
インスタンス生成後にサイズを増減でき、メモリを無駄遣いしない特徴を持つ。



今回の実装について

今回は以下の機能を実装する。

  • リストの先頭に要素を挿入
  • リストの末尾に要素を挿入
  • リスト内の要素取得
  • リスト内の要素探索
  • リストの要素数取得
  • リストの要素の削除

Nodeオブジェクト

Nodeオブジェクトは、データの実体を持つフィールド変数、次のNodeの参照オブジェクトのフィールド変数を保持する。
データの実体に関しては、JavaのObjectクラスとして、次のNodeクラスは自分自身のクラスろする。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Node {
    private Object data;
    private Node next;

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

連結リストオブジェクト

リストの先頭に要素を挿入

インスタンス生成時に指定した型の要素を先頭に挿入する。
生成したインスタンスに対して、先頭にオブジェクト の挿入するメソッドaddFirstを呼ぶことによって、追加することができる。
addFirstは先頭に挿入するメソッドなので、フィールド変数のNodeとNodeが保持する次のNodeの入れ替えを行う。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
   private Node node;
   
   /**
     * Add element for lead.
     *
     * @params data Generics
     */
    public void addFirst(T data) {
        Node node = new Node();
        node.data = data;
        node.next = this.node;
        this.node = node;
    }
}

リストの末尾に要素を挿入

インスタンス生成時に指定した型の要素を末尾に挿入する。
生成したインスタンスに対して、末尾にオブジェクト の挿入するメソッドaddを呼ぶことによって、追加することができる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
    private Node node;

        /**
     * Add element for last.
     *
     * @params data Generics
     */
    public void add(T data) {
        Node previousNode = this.node;
        Node currentNode = this.node.getNext();
        while (currentNode != null) {
            if (currentNode.getData().equals(data)) {
                previousNode.setNext(currentNode.getNext());
                return;
            }
            previousNode = currentNode;
            currentNode = currentNode.getNext();
        }

        Node node = new Node();
        node.setData(data);
        previousNode.setNext(node);
    }
}

リスト内の要素取得

リストのデータを取得するメソッドを実装する。
連結リストのインデックス値から取得する処理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
    private Node node;
    
    /**
     * Get element.
     *
     * @param position Position
     * @return Data
     */
    public T get(int position) {
        if (this.node == null) {
            return null;
        }

        Node currentNode = this.node;
        for (int i = 0; i < position; i++) {
            currentNode = currentNode.getNext();
        }

        return (T)currentNode.getData();
    }
}

リスト内の要素探索

リストに追加した際に、要素の探索をしたいケースが当然ある。
要素の探索をするメソッドを実装する。
要素が存在する場合はtrue、存在しない場合はfalseを返すcontains。

探索をするときは、リストが保持しているNodeオブジェクトの次の参照オブジェクトをforで回して順番に探索を行う。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
   private Node node;
  
   /**
     * Check contain data in LickedList.
     *
     * @params data Generics
     * @return true or false
     */
    public boolean contains(T data) {
        Node currentNode = this.node;
        while (currentNode != null) {
            if (currentNode.data.equals(data)) {
                return true;
            }
            currentNode = currentNode.next;
        }

        return false;
    }
}

リストの要素数

リストに追加したデータが合計何件あるのかをカウントするメソッドを実装する。
ArrayListクラスでも実装されているsizeメソッド。

sizeメソッドは、リストが保持しているNodeがnullになるまでの回数をカウントして、そのカウント数を返却する。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
   private Node node;
    
   /**
     * LinkedList size.
     *
     * @return size
     */
    public int size() {
        int count = 0;
        Node currentNode = this.node;
        while (currentNode != null) {
            count++;
            currentNode = currentNode.next;
        }
        return count;
    }
}

リストの要素の削除

リストに追加されたデータを削除するメソッドを実装する。

removeは削除したい要素から削除を行うメソッド、削除したい要素番号から削除を行うメソッドの二つを実装する。
また、前者の要素から削除するメソッドは冪等性があり、存在しない要素であってもすべて削除されたとみなすように実装する。一方、後者の要素番号から削除するメソッドは冪等性がなく、存在しない番号値であった場合はNullPointerExceptionとする。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
   private Node node;
   
   /**
     * Remove list data.
     * The paramter data is removing
     *
     * @params data Generics
     */
    public void remove(T data) {
        if (this.node == null) {
            return;
        }

        if (this.node.data.equals(data)) {
            this.node = this.node.next;
            return;
        }

        Node previousNode = this.node;
        Node currentNode = this.node.next;
        while (currentNode != null) {
            if (currentNode.data.equals(data)) {
                previousNode.next = currentNode.next;
                return;
            }
            previousNode = currentNode;
            currentNode = currentNode.next;
        }
    }

    /**
     * Remove list data from position.
     * The parameter position data is removing
     *
     * @params position Index of linked list
     */
    public void remove(int position) {
        if (this.node == null) {
            return;
        }

        if (position == 0) {
            this.node = this.node.next;
        }

        int currentPosition = 0;
        Node previousNode = this.node;
        Node currentNode = this.node.next;
        for (int i = 0; i <= position; i++) {
            if ((position-1) == i) {
                previousNode.next = currentNode.next;
                return;
            }
            previousNode = currentNode;
            currentNode = currentNode.next;
        }
    }
}

メイン関数から利用してみる

Mainクラス。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Main {
    public static void main(String args[]) {
        LinkedList<String> list = new LinkedList<String>();
        list.addFirst("test1");
        System.out.println(list);

        list.addFirst("test2");
        System.out.println(list);

        list.addFirst("sasa");
        System.out.println(list);
        
        list.remove(2);
        System.out.println(list);

        list.add("test3");
        System.out.println(list);

        list.add("test4");
        System.out.println(list);

        list.add("test5");
        System.out.println(list);

        for (int i = 0; i < list.size(); i++) {
            System.out.println(i + " element = " + list.get(i));
        }
    }
}

LinkedListクラス。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/**
 * Linked List data structure.
 * - Linked pointer
 * - The last element is null
 * - Don't waste memory
 */
public class LinkedList<T> {
    private Node node;

    /**
     * Get element.
     *
     * @param position Position
     * @return Data
     */
    public T get(int position) {
        if (this.node == null) {
            return null;
        }

        Node currentNode = this.node;
        for (int i = 0; i < position; i++) {
            currentNode = currentNode.getNext();
        }

        return (T)currentNode.getData();
    }

    /**
     * LinkedList size.
     *
     * @return size
     */
    public int size() {
        int count = 0;
        Node currentNode = this.node;
        while (currentNode != null) {
            count++;
            currentNode = currentNode.getNext();
        }
        return count;
    }
    
    /**
     * Add element for lead.
     *
     * @params data Generics
     */
    public void addFirst(T data) {
        Node node = new Node();
        node.setData(data);
        node.setNext(this.node);

        this.node = node;
    }
    
    /**
     * Add element for last.
     *
     * @params data Generics
     */
    public void add(T data) {
        Node previousNode = this.node;
        Node currentNode = this.node.getNext();
        while (currentNode != null) {
            if (currentNode.getData().equals(data)) {
                previousNode.setNext(currentNode.getNext());
                return;
            }
            previousNode = currentNode;
            currentNode = currentNode.getNext();
        }

        Node node = new Node();
        node.setData(data);
        previousNode.setNext(node);
    }

    /**
     * Check contain data in LickedList.
     *
     * @params data Generics
     * @return true or false
     */
    public boolean contains(T data) {
        Node currentNode = this.node;
        while (currentNode != null) {
            if (currentNode.getData().equals(data)) {
                return true;
            }
            currentNode = currentNode.getNext();
        }

        return false;
    }

    /**
     * Remove list data.
     * The paramter data is removing
     *
     * @params data Generics
     */
    public void remove(T data) {
        if (this.node == null) {
            return;
        }

        if (this.node.getData().equals(data)) {
            this.node = this.node.getNext();
            return;
        }

        Node previousNode = this.node;
        Node currentNode = this.node.getNext();
        while (currentNode != null) {
            if (currentNode.getData().equals(data)) {
                previousNode.setNext(currentNode.getNext());
                return;
            }
            previousNode = currentNode;
            currentNode = currentNode.getNext();
        }
    }

    /**
     * Remove list data from position.
     * The parameter position data is removing
     *
     * @params position Index of linked list
     */
    public void remove(int position) {        
        if (this.node == null) {
            return;
        }
        
        if (position == 0) {
            this.node = this.node.getNext();
        }

        Node previousNode = this.node;
        Node currentNode = this.node.getNext();
        for (int i = 0; i <= position; i++) {
            if ((position-1) == i) {
                previousNode.setNext(currentNode.getNext());
                return;
            }
            previousNode = currentNode;
            currentNode = currentNode.getNext();
        }
    }
    
    /**
     * Override method.
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        Node currentNode = this.node;
        while (currentNode != null) {
            builder.append(currentNode.getData());
            if (currentNode.getNext() != null) {
                builder.append(", ");
            }
            currentNode = currentNode.getNext();
        }
        builder.append(']');
        return builder.toString();
    }
}
FEATURED TAGS
Java データ構造