[자료구조] 3. 연결리스트(LinkedList) 구현하기 (Java)

연결 리스트(LinkedList)

①

 연결 리스트(LinkedList)는 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 아래 소스코드에서 구현한 연결 리스트는 각 노드가 데이터를 가지고 이전 노드와 다음 노드의 주소 값 2개를 저장하는 이중 연결 리스트(Dobly LinkedList) 구조입니다. 여기서 노드는 Node라는 클래스로 선언되어 있고 데이터(data),  이전 노드(prev), 다음 노드(next)로 구성되어 있습니다.

 

②

아래 소스코드에서 연결 리스트와 관련된 함수들은 다음과 같습니다.

addFirst(int data): 리스트의 맨 앞에 data를 추가하는 함수

addLast(int data): 리스트의 맨 뒤에 data를 추가하는 함수

add(int index, int data): 원하는 위치(index)에 data를 추가하는 함수

removeFirst(): 리스트의 맨 앞에 있는 데이터를 삭제하는 함수

removeLast(): 리스트의 맨 뒤에 있는 데이터를 삭제하는 함수

remove(int index): 원하는 위치(index)의 데이터를 삭제하는 함수

get(int index): 원하는 위치(index)의 데이터를 return하는 함수

getNode(int index): 원하는 위치(index)의 노드를 return하는 함수

 

③

 아래 소스코드의 맨 아래 주석 부분을 보면 Input과 Output을 알 수 있습니다. 문제에서 요구하는 Output은 연결 리스트에 넣은 데이터들을 2개 간격으로 하나씩 뺄 때 마지막에 남아있는 데이터를 출력하는 것입니다. 테스트 케이스의 개수는 2입니다.

 첫 번째 테스트 케이스를 보면 먼저 5개의 숫자가 들어옵니다. 1 2 3 4 5가 들어오면 순차적으로 연결 리스트에 저장합니다. 연결 리스트에서 데이터를 하나씩 삭제하는 과정을 살펴보면 1 2 3 4 5 -> 2 3 4 5 -> 2 3 5 -> 2 5 -> 2의 과정을 거쳐 2가 결과값으로 나옵니다.

 두 번째 테스트 케이스를 보면 6개의 숫자가 들어옵니다. 1 2 3 4 5 6이 들어오면 순차적으로 연결 리스트에 저장하고 데이터를 하나씩 삭제하는 과정을 살펴보면 1 2 3 4 5 6 -> 2 3 4 5 6 -> 2 3 5 6 -> 3 5 6 -> 3 5 -> 5의 과정을 거쳐 5가 결과값으로 나옵니다.

소스 코드

import java.util.Scanner;
 
class LinkedList { //LinkedList 클래스
    Node head, tail;
    int size;
    
    public LinkedList() { //LinkedList 클래스의 생성자
        size = 0;
    }
    
    private class Node { //Node 클래스 - 이중 연결리스트(Doubly LinkedList) 구조
        int data;
        Node prev;
        Node next;        
        public Node(int data) { //ListNode 클래스의 생성자
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }
    
    public void addFirst(int data) { //addFirst: List의 맨 앞(head)에 data를 추가하는 함수
        Node newNode = new Node(data);        
        if(head != null) { //맨 앞에 이미 data가 있는 경우
            newNode.next = head;
            head.prev = newNode;
        }        
        head = newNode;        
        if(head.next == null) { //data가 처음 들어간 경우
            tail = head;
        }
        size++; //data 추가에 따른 size +1 증가        
    }
    
    public void addLast(int data) { //addLast: List의 맨 뒤(tail)에 data를 추가하는 함수
        if(size == 0) { //List에 data가 존재하지 않는 경우 맨 앞에 data를 추가하는 것과 동일
            addFirst(data);
        }
        else {
            Node newNode = new Node(data);
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
            size++;
        }
    }
    
    public void add(int index, int data) { //add: 원하는 index 위치에 data를 추가하는 함수
        if(index == 0) addFirst(data);
        else if(index == size) addLast(data);
        else {
            Node newNode = new Node(data);
            Node prevNode = getNode(index - 1);
            Node nextNode = prevNode.next;
            
            newNode.prev = prevNode;
            newNode.next = nextNode;
 
            prevNode.next = newNode;
            nextNode.prev = newNode;
            
            size++;
        }
    }
    
    public void removeFirst() { //removeFirst: List의 맨앞에 있는 data를 삭제하는 함수
        if(size == 0) System.out.println("삭제할 data가 존재하지 않습니다.");
        else {
            Node removeNode = head;
            head = null;
            head = removeNode.next;
            head.prev = null;
            size--;
        }
    }
    
    public void removeLast() { //removeLast: List의 맨뒤에 있는 data를 삭제하는 함수
        if(size == 0) System.out.println("삭제할 data가 존재하지 않습니다.");
        else {
            Node removeNode = tail;
            tail = null;
            tail = removeNode.prev;
            tail.next = null;
            size--;
        }
    }
    
    public void remove(int index) { //remove: index위치의 data를 삭제하는 함수
        if(size == 0) System.out.println("삭제할 data가 존재하지 않습니다.");
        else if(index == 0) removeFirst();
        else if(index == size - 1) removeLast();
        else {
            Node removeNode = getNode(index);
            Node prevNode = removeNode.prev;
            Node nextNode = removeNode.next;
            
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
            size--;
        }
    }
    
    public int get(int index) { //get: index위치의 data를 return하는 함수
        return getNode(index).data;
    }
 
    private Node getNode(int index) { 
 //getNode: index가 size/2보다 작으면 head부터, 크다면 tail부터 탐색하여 해당하는 index의 node를 return하는 함수
        if(index < size / 2) {
            Node node = head;
            for(int i = 0; i<index; i++) {
                node = node.next;
            }
            return node;
        }
        else {
            Node node = tail;
            for(int i = size - 1; i>index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
    
}
 
class STL_LinkedList {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            LinkedList list = new LinkedList();
            int N = sc.nextInt();
            for (int i = 0; i < N; i++) {
                int data = sc.nextInt();
                list.add(i, data);
            }
            int index = 0;
            while (list.size>1) {
                list.remove(index);
                index = (index+2)%list.size;
            }
            System.out.printf("#%d %d\n", test_case, list.get(0));
        }
        sc.close();
    }
}
 
/*
input
2
5
1 2 3 4 5
6
1 2 3 4 5 6
output
#1 2
#2 5
*/