Java 링크드리스트 구현

안녕들 하시죠!

이번시간에는 Java 언어를 사용해 링크드리스트(이중 연결 리스트)를 구현해보겠습니다.

아래에는 제가 사용할 클래스와 메소드입니다.

 

public class LinkedList {
    
        Node head;
        Node rear;
        int size = 0;
    
        void firstNode(int data) {} // 첫번째 Node 생성
        void addRearNode(int data) {} // 뒷단에 Node 삽입
        void addHeadNode(int data) {} // 앞단에 Node 삽입
        int readData(int index) {} // 특정 데이터 읽기
        void printData() {} // 전체 데이터 출력
        boolean removeNode(int index) {} // 특정 노드 삭제
        boolean removeAllNode() {} // 전체 노드 삭제
        
        class Node {
            Node(int data) {
                this.data = data;
            }
            int data;
            Node front = null;
            Node back = null;
        }
}

 

기본적인 Node의 구성입니다.

값이 들어있는 data, 앞에있는 Node를 가리키고 있는 front, 뒤에있는 Node를 가리키고 있는 back

 

앞에있는 Node를 head, 뒤에있는 Node를 rear라고 구성합니다.

 

- void firstNode

 

void firstNode(int data) {
        Node newNode = new Node(data);
        head = newNode;
        rear = newNode;
        size++;
        System.out.println("firstNode(int data) 실행");
    }

 

Node가 한개도 없는 상황에서 첫번째 Node를 생성하는 메소드입니다.

앞,뒤에 어떤 Node도 존재하지 않기 때문에 head와 rear 둘다 첫번째 Node를 가리키게 됩니다.

Node가 생성되었으니 size를 증가시켜줍니다.

 

 

- void addRearNode

void addRearNode(int data) {
        if (size != 0) {
            Node newNode = new Node(data);
            rear.back = newNode; // ①
            newNode.front = rear; // ②
            rear = newNode; // ③
            size++;
            System.out.println("addRearNode(int data) 실행");
        } else {
            System.out.println("firstNode(int data) 실행시켜주세요");
        }
    }

 

맨뒤에 Node를 삽입하는 메소드입니다.

 

간단하게 생각하면,

현재 맨뒤를 가리키고 있는 rear의 뒷자리에 새로운 Node를 삽입하고 서로 가리키고있는 화살표를 바꿔주고 맨뒤에 새로 삽입된 Node를 rear로 만들어주는 과정입니다.

 

 

① : rear의 back의 뒤로 향하는 화살표를 새로 삽입될 newNode를 가리키게 만든다. ( rear.back = newNode )

② : 새로 삽입될 newNode의 앞으로 향하는 화살표를 현재 rear를 가리키게 만든다. ( newNode.front = rear )

③ : 화살표를 바꿔 서로 가리키게 만들었으니 새로 삽입될 newNode를 맨뒤(rear)로 만들어준다. ( rear = newNode )

 

- void addHeadNode

앞에서 설명한 addRearNode와 비슷하게 이번엔 맨앞단에 Node를 삽입하는 메소드입니다.

 

void addHeadNode(int data) {
        if (size != 0) {
            Node newNode = new Node(data);
            head.front = newNode; // 현재 가장 앞에있는 head Node의 앞으로 향하는 화살표가 새로 삽입될 newNode를 가리키게 만든다.
            newNode.back = head; // 새로 삽입될 newNode의 뒤로 향하는 화살표가 현재 head인 Node를 가리키게 만든다.
            head = newNode; // 새로 삽입될 newNode를 맨앞(head)로 만들어준다. 
            size++;
            System.out.println("맨앞에 " + data + " 들어감");
        } else {
            firstNode(data); // 현재 삽입되어있는 Node가 없다면 새로 추가.
        }
    }

 

 

 

- int readData

특정 Node의 data 읽기.

int readData(int index) {
        int result = 0;
        try {
            Node node = head; // 맨앞 Node 부터 시작.
            for (int i = 1; i < index; i++) {
                node = node.back; // 한칸씩 뒤로 이동하며 특정위치(index)를 찾고, 값을 result에 저장.
            }
            result = node.data;
        } catch (Exception e) {
            System.out.println("Exception 발생");
        }
        return result;
    }

 

- void printData

전체 Node의 data 출력.

 

void printData() { 
        if (size > 0) {
            try {
                Node node = head; // 맨앞 Node부터 시작.
                for (int i = 0; i < size; i++) {
                    System.out.print(node.data + " ");
                    node = node.back; // 한칸씩 뒤로 이동하며 모든 Node의 data 출력.
                }
            } catch (Exception e) {
                System.out.println("Exception 발생");
            }
        } else {
            System.out.println("출력데이터가 없습니다.");
        }
    }

 

- boolean removeNode

특정위치의 Node 삭제.

boolean removeNode(int index) {
        if ((index <= size && index > 0) && size > 0) {
            if (index == 1) {// head를 지울때
                head = head.back; // head를 뒤로 한칸 옮긴다.
                head.front = null;
            } else if (index == size) {// rear를 지울때
                rear = rear.front; // rear를 한칸 앞으로 옮긴다.
                rear.back = null;
            } else { // head나 rear가 아닌 중간에 있는 Node를 지울때
                Node node = head;
                for (int i = 1; i < index; i++) {
                    node = node.back;
                }
                node.front.back = node.back; // ①
                node.back.front = node.front;
            }
            size--;
            return true;
        } else {
            System.out.println("index 범위X");
            return false;
        }
    }

 

 

① : 중간에 있는 Node를 삭제했으니, 앞 뒤의 Node들을 화살표로 연결해 주는 과정입니다.

 

- boolean removeAllNode

전체 Node 삭제.

boolean removeAllNode() {
        head = null;
        rear = null;
        size = 0;
        return true;
    }

 

LinkedList 전체 코드

public class Linkedlist {
 
    Node head;
    Node rear;
    int size = 0;
    
    // 아무것도 없는 상태에서 새로운 Node 추가
    void firstNode(int data) {
        Node newNode = new Node(data);
        head = newNode;
        rear = newNode;
        size++;
        System.out.println("firstNode(int data) 실행");
    }
 
    // 뒷단에 Node 추가
    void addRearNode(int data) {
        if (size != 0) {
            Node newNode = new Node(data);
            rear.back = newNode; // ①
            newNode.front = rear; // ②
            rear = newNode; // ③
            size++;
            System.out.println("addRearNode(int data) 실행");
        } else {
            System.out.println("firstNode(int data) 실행시켜주세요");
        }
    }
 
    // 맨앞단에 Node 추가
    void addHeadNode(int data) {
        if (size != 0) {
            Node newNode = new Node(data);
            head.front = newNode; // 현재 가장 앞에있는 head Node의 앞으로 향하는 화살표가 새로 삽입될 newNode를 가리키게 만든다.
            newNode.back = head; // 새로 삽입될 newNode의 뒤로 향하는 화살표가 현재 head인 Node를 가리키게 만든다.
            head = newNode; // 새로 삽입될 newNode를 맨앞(head)로 만들어준다. 
            size++;
            System.out.println("맨앞에 " + data + " 들어감");
        } else {
            firstNode(data); // 현재 삽입되어있는 Node가 없다면 새로 추가.
        }
    }
 
    // 특정 위치(index) Node Data 읽기
    int readData(int index) { // 특정 노드의 data 읽기
        int result = 0;
        try {
            Node node = head; // 맨앞 Node 부터 시작.
            for (int i = 1; i < index; i++) {
                node = node.back; // 한칸씩 뒤로 이동하며 특정위치(index)를 찾고, 값을 result에 저장.
            }
            result = node.data;
        } catch (Exception e) {
            System.out.println("Exception 발생");
        }
        return result;
    }
 
    // 전체 노드의 data 출력
    void printData() { 
        if (size > 0) {
            try {
                Node node = head; // 맨앞 Node부터 시작.
                for (int i = 0; i < size; i++) {
                    System.out.print(node.data + " ");
                    node = node.back; // 한칸씩 뒤로 이동하며 모든 Node의 data 출력.
                }
            } catch (Exception e) {
                System.out.println("Exception 발생");
            }
        } else {
            System.out.println("출력데이터가 없습니다.");
        }
    }
 
    // 특정 위치(index) Node 삭제
    boolean removeNode(int index) {
        if ((index <= size && index > 0) && size > 0) {
            if (index == 1) {// head를 지울때
                head = head.back; // head를 뒤로 한칸 옮긴다.
                head.front = null;
            } else if (index == size) {// rear를 지울때
                rear = rear.front; // rear를 한칸 앞으로 옮긴다.
                rear.back = null;
            } else { // head나 rear가 아닌 중간에 있는 Node를 지울때
                Node node = head;
                for (int i = 1; i < index; i++) {
                    node = node.back;
                }
                node.front.back = node.back; // ①
                node.back.front = node.front; // ②
            }
            size--;
            return true;
        } else {
            System.out.println("index 범위X");
            return false;
        }
    }
 
    // 전체 Node 삭제
    boolean removeAllNode() {
        head = null;
        rear = null;
        size = 0;
        return true;
    }
 
    class Node {
        Node(int data) {
            this.data = data;
        }
 
        int data;
        Node front = null;
        Node back = null;
    }
}

 

오늘은 여기까지입니다 감사합니다 !