Singly Linked List(단일 연결 리스트) (Java)

새로운 노드를 insert할 때마다, 이전에 있던 노드들과 새 노드를 대소 비교한다. 그러면서 더 큰 값이 start(head)와 가깝게, 즉 내림차순으로 list를 형성한다.

package LinkedList;

public class SinglyLinkedList {
    class Node {
        int data;
        Node next;

        Node(int data) {this.data = data;}

        Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

    }

    int size = 0;// 연결 리스트에 저장된 원소의 개수
    Node start = null; //연결 리스트를 가리키는 레퍼런스 , start == head

    // x를 list에 내림차순으로 삽입하는 메서드
    void insert(int x){
        size++;
        Node newNode = new Node(x);
        if (start == null) {
            start = newNode;
            return;
        }


        Node existing = start;
        while (existing != null) {
            if (existing.data > newNode.data) {
                if (existing.next == null) {
                    existing.next = newNode;
                    return;
                }
                if (existing.next.data <= newNode.data) {
                    newNode.next = existing.next;
                    existing.next = newNode;
                    return;
                }
                else {
                    existing = existing.next;
                }
                // 위에서 처리해주었기 때문에 이 조건문은 start와 newNode가 같은 경우를 따지는 조건문이다.
            }
            else if (existing.data <= newNode.data) {
                newNode.next = start;
                start = newNode;
                return;
            }
        }

        System.out.println("[insert] 제대로 연결되지 않았습니다."); //디버깅 위한 출력문
        return;
    }

    // 연결 리스트의 값을 차례대로 출력하는 메서드
    void print() {
        Node node = start;
        System.out.printf("size: %d | ", size);
        while (node != null) {
            System.out.printf(node.data+" ");
            node = node.next;
        }
        System.out.println();
    }
}

---

아래는 위의 연결 리스트를 실행하는 Main 클래스이다.

ipnut file을 따로 만들어두었기 때문에 아래처럼 Filereader로 file을 읽어와서 처리했다.

package LinkedList;

import java.io.*;

public class MainLinkedList {
    public static void main(String[] args) throws IOException {
        SinglyLinkedList ll = null;
        BufferedReader br = new BufferedReader(new FileReader("C:\\Users\\user\\IdeaProjects\\testProject\\src\\LinkedList\\input.txt"));

        String str;
        String[] stringlist;
        int count = 0;
        while((str = br.readLine()) != null){
            ll = new SinglyLinkedList();

            System.out.printf("[%d번 째 줄 리스트]\n", ++count);
            stringlist = str.split(" ");
            for (String tmp : stringlist) {
                ll.insert(Integer.parseInt(tmp));
                ll.print();
            }
            System.out.println("= = = = = = = = = = = = = =");
        }
    }
}

input.txt
4 2 9 6 7
-1 8 4 10 -5 0

---

Run

 

[1번 째 줄 리스트]
size: 1 | 4 
size: 2 | 4 2 
size: 3 | 9 4 2 
size: 4 | 9 6 4 2 
size: 5 | 9 7 6 4 2 
= = = = = = = = = = = = = =
[2번 째 줄 리스트]
size: 1 | -1 
size: 2 | 8 -1 
size: 3 | 8 4 -1 
size: 4 | 10 8 4 -1 
size: 5 | 10 8 4 -1 -5 
size: 6 | 10 8 4 0 -1 -5 
= = = = = = = = = = = = = =