34. LinknedList

Isaiah IM·2023년 11월 22일
Java
0

java basic

목록 보기
36/38
post-thumbnail

1. Linkend List란?

1.1 Linkend List의 개념

linked List란 기존의 배열을 이용한 ArrayList의 단점을 개선한 자료구조로, 크기를 자유롭게 변경할 수 있는 자료구조이다.

이때, Linked List에서 데이터가 저장되는 것을 node라고 하며, 각 노드가 유기적으로 연결되기 때문에 데이터의 추가/삭제가 비교적 자유롭다. 이때. 각 노드가 연결될 수 있는 이유는 노드는 데이터를 저장하는 영역과 연결할 노드의 주소를 저장하는 영역으로 나뉘어져 있기 때문이다.

1.2 Linkend List 추가/삭제 연산

Linked List에는 추가 및 삭제가 가능한 메소드가 있다.
참고로 상남자 언어인 C언어에서는 그런거 없이 직접 다 만들어야 한다.

1.2.1 추가 연산

메소드:
.add(Object o): 객체를 리스트의 맨 끝에 추가.
.add(int index, Object o): 객체를 특정한 위치(index)에 저장
.addFirst(Object o): 객체를 리스트의 맨 앞에 추가
.offerFirst(Object o): 객체를 리스트의 맨 앞에 추가(실패시 false반환)
.addLast(Object o): 객체를 리스트의 맨 끝에 추가
.offerLast(Object o): 객체를 리스트의 맨 끝에 추가(실패시 false반환)

추가 연산 원리:
리스트는 다음과 같은 구조이다.

위 그림을 보면 노드에 있는 데이터(0x100 등..)이 다음 노드의 주소를 가리킨다. 이때, 노드를 삽입하는 방법은 크게 3가지가 있다.

  • 맨 앞에 추가
    새로운 노드를 맨 앞에 추가하는 방법은 아래 그림과 같다.
    먼저 아래 그림과 같이 노드를 먼저 생성한다.

    다음으로 맨 앞 노드(보통은 뚝빼기head라고 부른다)의 주소를 새로운 노드에 있는 주소를 입력하는 부분(보통은 링크라고 부른다) 입력한다.

    이렇게 하면 노드가 맨 앞에 추가된다.

  • 가운데에 추가
    가운데에 새로운 노드를 추가하는 방법은 다음과 같다.
    아래 그림처럼 먼저, 새로운 노드를 만든다.

    다음으로 아래 그림과 같이 새로운 노드의 링크 부분에 연결할 주소를 입력한다.

    다음으로 앞쪽 노드의 링크에 새로운 노드의 주소를 입력하면 된다.

    이와 같이 하면 아래 그림과 같이 새로운 노드가 중간에 추가된다.

  • 맨 뒤에 추가
    새로운 노드를 맨 뒤에 추가하는 방법은 아래 그림과 같다.
    먼저 아래 그림과 같이 노드를 먼저 생성한다.

    다음으로 맨 뒤 노드(보통은 tail이라고 부른다)의 주소를 새로운 노드에 있는 링크에 복사한다.

    마지막으로, 위의 그림과 같이 새로운 노트의 주소롤 기존의 tail 노드의 링크에 입력한다.

    이렇게 하면 노드가 맨 뒤에 추가된다.

1.2.2 삭제 연산

메소드:
.remove(Object o): 해당 객체를 리스트에서 삭제
.remove(int index): 특정한 위치(index)에 있는 객체를 삭제
.poll(): 리스트의 맨 앞에 있는 객체를 삭제(삭제한 객체 반환)

삭제 연산 원리:
리스트의 노드를 삭제하는 방법은 크게 2가지가 있다.

  • 맨 앞 노드 삭제
    만 앞의 노드를 삭제하는 방법은 다음과 같다.
    먼저 아래 그림과 같이 head 노드를 찾는다.

    다음으로 head 노드의 링크의 주소를 head의 주소로 업데이트 하고, 기존의 head 노드는 삭제한다.

    이렇게 하면 노드가 맨 앞에 추가된다.
  • 가운데 노드 삭제
    가운데에 있는 노드를 삭제하는 방법은 다음과 같다.
    아래 그림처럼 삭제할 노드를 찾는다.

    다음으로 아래 그림과 같이 삭제할 노드에 있는 링크를 삭제할 노드 이전의 노드의 링크에 복사한다.

    이렇게 하면 삭제하려는 노드의 이전 노드와 삭제할 노드 다음의 노드가 연결된다.
    마지막으로 아래와 같이 노드를 삭제한다.

1.3 Linkend List vs 배열

위에서 본 것과 같이 LinkedList는 일반적인 배열과 삭제/삽입에서 차이가 있다.
만약 리스트 자료구조중 배열을 기반으로한 ArrayList와 노드를 기반으로 한 LinkedList중 선택해야 한다면 각 특징에 맞게 효율적인 선택을 할 필요가 있다.
효율적으로 선택하기 위한 기준은 다음과 같다.

  1. 저장해야 하는 데이터의 갯수가 가변적인가(예측이 불가능한가)?
    -> 데이터의 갯수가 예측이 불가능하면 ArrayList의 초기 용량을 예측하기 어렵기 때문에 LinkedList를 사용하는 것이 더 효율적이다.

  2. 데이터의 검색이 자주 일어나는가?
    -> LinkedList의 경우 데이터를 검색할때 모든 노드를 일일히 순회해야 하기 때문에 시간이 오래 걸리므로, 배열을 기반으로 한 ArrayList를 사용하는 것이 더 효율적이다.

  3. 데이터의 삽입/삭제가 자주 일어나는가?
    -> 데이터의 삽입/삭제 연산은 ArrayList에서는 빈 공간을 없애기 위한 추가적인 작업이 필요하므로, LinkedList가 더 효율적이다.

위와 같은 기준으로 선택을 하면 보다 효율적인 자료구조를 선택할 수 있다.

2. LinkedList의 활용

2.1 LinkedList의 기본 사용법

LinkedList를 생성후, 기본적인 입출력은 다음과 같이 할 수 있다.

import java.util.LinkedList;// import 해야 사용할 수 있음.

public class Main {
    public static void main(String[] args){
        LinkedList list = new LinkedList();

        /*리스트에 추가하는 연산*/
        list.add("String");
        list.add("스트링 치즈");
        list.add("먹고싶다.");

        list.add("cheese");
        list.add("is");
        list.add("truth.");

        list.add("치즈는");
        list.add("진리다.");

        System.out.println("---list print---");
        System.out.println(list);

        list.remove("String");
        System.out.println(" \"String\" is deleted.");
        System.out.println("---list print---");
        System.out.println(list);

        list.remove(0);
        System.out.println(" 0 index is deleted");
        System.out.println("---list print---");
        System.out.println(list);

        list.remove(0);
        System.out.println(" 0 index is deleted");
        System.out.println("---list print---");
        System.out.println(list);
    }
}

output

---list print---
[String, 스트링 치즈, 먹고싶다., cheese, is, truth., 치즈는, 진리다.]
 "String" is deleted.
---list print---
[스트링 치즈, 먹고싶다., cheese, is, truth., 치즈는, 진리다.]
 0 index is deleted
---list print---
[먹고싶다., cheese, is, truth., 치즈는, 진리다.]
 0 index is deleted
---list print---
[cheese, is, truth., 치즈는, 진리다.]


치즈는 사랑이다♥

그러나, 현실에서는 제네릭을 같이 활용해서 다음과 같이 작성하곤 한다.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args){
        LinkedList<String> list = new LinkedList();// <>제네릭 사용.
        
        /*리스트에 추가하는 연산*/
        list.add("String");
        list.add("스트링 치즈");
        list.add("먹고싶다.");

        list.add("cheese");
        list.add("is");
        list.add("truth.");

        list.add("치즈는");
        list.add("진리다.");

        System.out.println("---list print---");
        System.out.println(list);

        list.remove("String");
        System.out.println(" \"String\" is deleted.");
        System.out.println("---list print---");
        System.out.println(list);

        list.remove(0);
        System.out.println(" 0 index is deleted");
        System.out.println("---list print---");
        System.out.println(list);

        list.remove(0);
        System.out.println(" 0 index is deleted");
        System.out.println("---list print---");
        System.out.println(list);
    }
}

제네릭은 아직 안배웠으니 나중에 자세히 다루도록 하며, 일단 리스트같은 자료구조는 대부분 제네릭과 같이 사용한다라고 알아두자.

2.2 LinkedList 활용

LinkedList에서 특정 객체를 검색하는 것은 .contains()과 .indexof() 메소드를 사용한다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args){
        LinkedList<String> list = new LinkedList();
        int idx;

        /*리스트에 추가하는 연산*/
        list.add("String");
        list.add("스트링 치즈");
        list.add("먹고싶다.");

        list.add("cheese");
        list.add("is");
        list.add("truth.");

        list.add("치즈는");
        list.add("진리다.");

        System.out.println("---list print---");
        System.out.println(list);

        /*"스트링 치즈" 객체 삭제*/
        if(list.contains("스트링 치즈")){
            idx=list.indexOf("스트링 치즈");
            list.remove(idx);
        }

        System.out.println("---list print---");
        System.out.println(list);
    }
}

3. Mini Project

LinkedList를 이용해 도서 관리 시스템을 만들어 보자.
도서관리 시스템에서는 다음과 같은 메뉴가 있다.
1. 책 추가
2. 책 삭제
3. 책 검색
4. 책 목록 출력
5. 종료

책은 오직 책 이름으로 추가/삭제/검색이 가능하며, 종료 버튼(5)를 눌러야 프로그램이 종료된다.

4. Mini Project 정답

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        LinkedList<String> bookList = new LinkedList();
        Scanner sc = new Scanner(System.in);
        int menu;
        String book_name;

        do{
            System.out.println("\n\n---------메뉴---------");
            System.out.println("1. 책 추가.");
            System.out.println("2. 책 삭제.");
            System.out.println("3. 책 검색.");
            System.out.println("4. 책 목록 출력.");
            System.out.println("5. 종료.");

            menu = Integer.parseInt(sc.nextLine());
            switch(menu){
                case 1:
                    System.out.print("추가할 책 이름: ");
                    book_name= sc.nextLine();

                    bookList.add(book_name);// 책 추가
                    System.out.println("책이 추가됬습니다.");
                    break;

                case 2:
                    System.out.print("삭제할 책 이름: ");
                    book_name= sc.nextLine();

                    if(bookList.contains(book_name) ){
                        bookList.remove(book_name);
                        System.out.println("책이 삭제됬습니다.");
                    }
                    else{
                        System.out.println("책이름이 잘못됬습니다.");
                    }
                    break;

                case 3:
                    System.out.print("검색할 책 이름: ");
                    book_name= sc.nextLine();

                    if(bookList.contains(book_name) ){
                        int index;
                        index=bookList.indexOf(book_name);
                        System.out.println("책이 "+index+" 번째에 있습니다.");
                    }
                    else{
                        System.out.println("해당 이름의 책이 없습니다..");
                    }
                    break;

                case 4:
                    int i=1;
                    for(String name : bookList){
                        System.out.println(i+". "+name);
                        i++;
                    }
                    break;

                case 5:
                    break;

                default:
                    System.out.println("해당 메뉴는 존재하지 않습니다.");
            }
        } while(menu!=5);


    }
}

ArrayList와 LinkedList 역시 모두 List 자료구조이기 때문에 자주 사용하는 메소드가 동일하다.

profile
Isaiah IM
나는 생각한다. 고로 나는 코딩한다.
이전 포스트

33. ArrayList

다음 포스트

35. stack, queue, deque

0개의 댓글