자바_Linked List

1. 링크드 리스트(Linked List)란?

- 연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.

 

- 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다.

 

 

2. 구현 방법

오늘 학원에서 배운 링크드 리스트를 자바로 직접 구현한 것을 포스팅해 보도록 하겠다.

 

[Node.java]

public class Node {
    //
    // -- Fields Area --
    //
    // 다음번 노드를 가리키는 참조(주소, 포인터)
    private Node next = null;
    
    // 실제 데이터(값)
    private int data = 0;
    
    
    //
    // -- Constructor Area --
    //
    public Node(int _data) {
        this.data = _data;
    }
    
    
    //
    // -- Getter and Setter Area --
    //
    public void    setNext(Node _node) { this.next = _node; }    
    public Node    getNext()           { return this.next; }
    public void    setData(int _data)  { this.data = _data; }
    public int     getData()           { return this.data; }
    
    
    //
    // -- Public Area --
    //
    public boolean hasNext() { return this.next != null; }
}

 

 

[MyLinkedList.java]

// Single-Linked List*
// Double-Linked List
public class MyLinkedList {
    //
    // -- Fields Area --
    //
    // 1. 헤드가 무조건 존재한다.
    // 2. 헤드와 테일이 무조건 존재한다.
    // 3. 둘 다 없음.
    private Node head = null;
    
    
    //
    // -- Constructor Area --
    //
    public MyLinkedList() {}
    
    
    //
    // -- Public Area --
    //
    public void add(int _data) {
        // 새로운 노드 생성
        Node newNode = new Node(_data);
        
        // 노드가 없다면, 헤드에 새로운 노드 추가
        if (isEmpty()) {
            head = newNode;
            return;
        }
        
        // 노드가 있다면, 제일 마지막 노드를 찾아서 새로운 노드 추가
        Node lastNode = getLastNode();
    
        // 새로운 노드를 마지막 노드의 다음으로 지정
        lastNode.setNext(newNode);
        //getLastNode().setNext(newNode);
    }
    
    public void add(int _idx, int _data) {
        // 1. 인덱스는 0 보다 작으면 안됨
        if (_idx < 0) return;
        // 2. 인덱스는 길이를 벗어나면 안됨
        if (_idx >= count()) return;
        
        // 노드 생성
        Node newNode = new Node(_data);
        
        // 만약에 인덱스가 0인 경우
        if (_idx == 0) {
            newNode.setNext(head);
            head = newNode;
            return;
        }
        
        // 삽입을 원하는 인덱스의 "이전" 인덱스 노드 찾기
        int findIdx = _idx - 1;
        int idx = 0;
        Node iterNode = head;
        while (idx < findIdx) {
            iterNode = iterNode.getNext();
            ++idx;
        }
        // Unit Test
        System.out.println(
                "Find Node: " + idx + " / " + iterNode.getData());
        
        // 노드 추가
        // 1. Prev -> Next
        // 2. Prev -> Next
        //    New -> Next(Prev -> Next)
        // 3. Prev -> New
        newNode.setNext(iterNode.getNext());
        iterNode.setNext(newNode);
    }
    
    public void removeFirst() {
        if (isEmpty()) return;
        head = head.getNext();
    }
    
    public void removeLast() {
        if (isEmpty()) return;
        
        // 노드가 하나 밖에 없다면 헤드를 지우면 됨
        if (count() == 1) {
            head = null;
            return;
        }
        
        Node iterNode = head;
        while (iterNode.getNext().getNext() != null) {
            iterNode = iterNode.getNext();
        }
        // 마지막 전 노드
        iterNode.setNext(null);
    }
    
    public void remove(int _idx) {
        if (_idx < 0) return;
        if (_idx >= count()) return;
        
        // 첫 번째 노드를 제거하는 경우 헤드 다음 노드로 교체
        if (_idx == 0) {
            head = head.getNext();
            return;
        }
        
        // 제거 해야하는 노드의 "이전" 노드 찾기
        Node iterNode = head;
        int idx = 0;
        while (idx < _idx - 1) {
            iterNode = iterNode.getNext();
            ++idx;
        }
        System.out.println("Find Node: " + idx + " / " + iterNode.getData());
        
        // 노드 제거와 이어붙이기
        iterNode.setNext(iterNode.getNext().getNext());
    }
    
    public boolean isEmpty() {
        return head == null;
    }
    
    public int count() {
        if (isEmpty()) return 0;
        
        Node iterNode = head;
        // 이미 헤드가 카운딩 된 것이기 때문에 1부터 시작
        int cnt = 1;
        while (iterNode.hasNext()) {
            iterNode = iterNode.getNext();
            ++cnt;
        }
        
        return cnt;
    }
    
    public void printAll() {
        if (isEmpty()) {
            System.out.println("EMPTY!!");
            return;
        }
        
        System.out.println("-- " + count() + " --");
        
        Node iterNode = head;
        int idx = 0;
        while (iterNode != null) {
            System.out.println(idx + ": " + iterNode.getData());
            iterNode = iterNode.getNext();
            ++idx;
        }
    }
    
    
    //
    // -- Private Area --
    //
    private Node getLastNode() {
        Node iterNode = head;
        // 현재 노드에서 다음번 노드가 있다면,
        while (iterNode.hasNext()) {
            // 현재 노드를 다음번 노드로 갱신
            iterNode = iterNode.getNext();
        }
        return iterNode;
    }
}

 

 

[Main.java]

public class Main {
    public static void main(String[] args) {
        MyLinkedList myList = new MyLinkedList();
        myList.printAll();
        myList.add(10);
        myList.add(20);
        myList.add(30);
        myList.printAll();
        myList.add(2, 100);
        myList.printAll();
        
        myList.remove(2);
        myList.printAll();
    }
}