[자료구조] LinkedList

LinkedList란??

 

변수와 다음 노드를 가리키는 정보를 가진 노드들의 집합

 

Java에서는 LinkedList와 ArrayList를 기본제공한다.

 

기본제공 메서드 

 

List<String> list = new ArrayList<>();  // String타입 리스트 기본 생성자 

 

get(int index) 

index위치의 값을 반환

contains(Object e)

해당 Object가 list에 있는지 boolean타입으로 반환

size()

list의 사이즈를 int로 반환

add(String e)

list에 String 추가

add(int index, String element)

list의 index위치에 String 추가

remove(int index)

해당 index 위치의 값을 삭제

clear()

list 초기화

 

 

 

직접 구현해보기 

 

public class Node {
    private Object data;
    private Node next;

    public Node() {
        data = null;
        next = null;
    }


    public Node(Object data) {
        this.data = data;
        next = null;
    }

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

    public Object getData() {
        return data;
    }
    public Node getNext() {
        return next;
    }

    // 리스트 맨 뒤에 추가
    public void add(int data) {
        if(this.data == null) {
            this.data = data;
        } else {
            Node newNode = this;
            while (newNode.getNext() != null) {
                newNode = newNode.getNext();
            }
            newNode.setNext(new Node(data));
        }
    }
    // idx 위치의 값을 return
    public Object get(int idx) {
        if(size() >= idx) {
            Node current = this;
            for(int i = 0; i < idx; i++) {
                current = current.getNext();
            }
            if(current == null) {
                return null;
            } else {
                return current.getData();
            }
        } else {
            return null;
        }
    }
    // 해당위치 삭제
    public boolean delete(int idx) {

        if(size() >= idx) {
            if(idx == 0) {
                this.data = this.next.getData();
                this.next = this.next.getNext();

                return true;
            }
            Node previous = this;
            Node current = this.next;
            for(int i = 0; i < idx-1; i++) {
                previous = current;
                current = current.getNext();
            }
            if(current != null) {
                previous.setNext(current.getNext());
            } else {
                previous.setNext(null);
            }
            return true;
        } else {
            return false;
        }
    }


    // 리스트 크기
    public int size() {
        int result = 0;
        if(this.data == null) {
            return result;
        } else {
            result++;
            if (this.next != null) {
                Node current = this.next;
                while (current != null) {
                    result++;
                    current = current.getNext();
                }
            }
            return result;
        }
    }
    // 리스트 출력
    public void print() {
        Node current = this;
        while(current != null) {
            System.out.println(current.getData());
            current = current.getNext();
        }
    }
}

 

 

메인함수

import java.util.Scanner;

public class Main {

    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {

        Node head = new Node();
        String status;
        while(true) {
            System.out.println("삽입 - insert\n삭제 - delete\n리스트출력 - print\nN번째 인덱스 출력 - index\n종료 - exit");
            status = scanner.nextLine();
            switch(status) {
                case "insert" -> {
                    head.add(getNumber());
                }
                case "delete" -> {
                    if(head.delete(getNumber())) {
                        System.out.println("삭제되었습니다.");
                    } else {
                        System.out.println("삭제할수없습니다");
                    }
                }
                case "print" -> {
                    head.print();
                }
                case "index" -> {
                    int index =  getNumber();
                    Object result = head.get(index);
                    if(result != null) {
                        System.out.println("List의 "+index+"번 값은 "+result+"입니다.");
                    } else {
                        System.out.println("존재하지않는 번호입니다.");
                    }
                }
                default -> {
                    return;
                }
            }

        }
    }
    public static int getNumber() {
        System.out.println("숫자를 입력해주세요");
        return Integer.parseInt(scanner.nextLine());
    }
}