List 자료구조

2023. 3. 24. 23:19·Algorithm

- 선형 자료구조- 순서를 가진 항목들의 모임

- 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는

데이터 적재라는 새로운 장점을 취한 자료구조
- 중복된 데이터의 저장 허용
- ArrayList , LinkedList등 여러 인터페이스를 구현한 자료형이 있다
- 자바스크립트,파이썬 같은 경우에는 리스트를 따로 구현하지 않고

배열에 List의 기능 중 일부를 제공
- List에서는 인덱스가 중요하지 않다
- 리스트의 핵심은 element간의 순서
- 다른말로 순서라는 의미의 시퀀스(sequence)라고도 함
- 수학적으로 유한수열을 표현한 것
 
기능(operation)
- 처음,끝에 데이터 삽입기능
- 리스트에 데이터가 있는지를 체크하는 기능
- 리스트의 모든 데이터에 접근할 수 있는 기능 


 

ArrayLsit

- 배열을 이용해서 리스트를 구현한 것을 의미
- 장점 : 내부적으로 배열을 이용하기 때문에 인덱스를 이용하여 접근하는 것이 빠름 
- 단점 : 데이터의 추가/삭제가 느림
- 내부적으로 데이터를 배열에 저장 하므로 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면 이후의 데이터들이 한칸씩 뒤로 물러나야 함 
- 삭제 : 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한 칸씩 땡겨야 함
- 데이터 가져오기 : 인덱스를 이용하기 때문에 메모리상의 주소를 정확하게 참조 하므로 속도가 매우 빠름
- 제네릭 타입을 선언한다면 해당 타입만 추가가능
- 기본적으로 리스트의 맨 뒤에 데이터 추가
- 특정 인덱스를 선택해 해당 위치에 데이터 추가 가능
- 데이터를 추가하는 과정에서 내부적으로 사용하는 배열이 꽉차면 기존의 배열 대비 2배 큰 새로운 배열을 만들고 기존의 데이터를 새로운 배열로 복제
- 사용자는 ArrayList의 크기에 신경쓰지 않고 편리하게 프로그램을 만들 수 있다

ArrayList<String> list = new ArrayList<>(); // 선언

ArrayList<String> list = new ArrayList<>(10); // 크기 지정 가능 

list.add("a"); // 값 추가

list.add(null); // null도 추가 가능

list.add(0, "b"); // 0번째 index에 5 추가

list.addAll(list2); // list 전체 복사

list.remove(0); // 해당 index의 값 제거

list.clear(); // ArrayList 값 모두 제거

list.size(); // ArrayList 크기 리턴

list.get(0); // 0번째 index 값 리턴

list.contains("a"); // ArrayList에 해당 값이 존재하면 true

list.indexOf("a"); // ArrayList에 해당 값이 존재하면 index, 없으면 -1 리턴

 
 
LinkedList

- 장점 : 데이터 공간을 미리 할당할 필요 없음,
즉, 리스트의 길이가 가변적이라 데이터 추가/ 삭제 용이
 
- 단점 : 연결 구조를 위한 별도 데이터 공간 필요
연결 정보를 찾는 시간이 필요(접근속도가 상대적으로 느림)
데이터 추가, 삭제 시 앞 뒤 데이터의 연결을 재구성하는 작업 필요
 
- 각 데이터를 노드라고 부르며, 배열에서 자주 삽입, 삭제가 이루어지는 경우 용이하여 ArrayList보다 선호된다.
- 하지만 ArrayList보다 검색에 있어서는 느리다는 단점이 있다.
- element간 연결(link)을 통해서 리스트를 구현한 것
- 노드(node or vertex)가 사용됨
- head(첫번째 node)와 tail(마지막 node)
- 메모리 제한이 없다
- 자료의 순서를 유지한 채 삽입과 제거가 쉽다
- 데이터를 링크로 연결해서 관리하는 자료구조
- 자료의 순서는 정해져 있지만, 연속성이 보장되는 않음
- 데이터 저장 단위로, 값과 포인터로 구성
 

 

LinkedList<Integer> list = new LinkedList<>(); // 선언

// LinkedList는 초기 크기 지정 불가능


list.addFirst(1); // 가장 앞에 값 추가

list.addLast(2); // 가장 뒤에 값 추가

list.add(3); // 값 추가

list.add(1, 10); // 1번 index에 값 추가

list.removeFirst(); // 가장 앞의 값 제거

list.removeLast(); // 가장 뒤의 값 제거

list.remove(1); // index 1에 해당하는 값 제거

list.remove(); // 생략시 0번 index 값 제거

list.clear(); // 모든 값 제거


list.size(); // LinkedList 크기 리턴

list.get(0); // 0번째 index 값 리턴

list.contains("a"); // LinkedList 해당 값이 존재하면 true

list.indexOf("a"); // LinkedList 해당 값이 존재하면 index, 없으면 -1 리턴

 

Stack

- 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
- 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 
- 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
- 그래프의 깊이 우선 탐색(DFS)에서 사용
- 재귀적(Recursion) 함수를 호출 할 때 사용

Stack<Integer> stack = new Stack<>(); //int형 스택 선언

Stack<String> stack = new Stack<>(); //char형 스택 선언


Stack<Integer> stack = new Stack<>(); //int형 스택 선언

stack.push(1);     // stack에 값 1 추가

stack.push(2);     // stack에 값 2 추가

stack.push(3);     // stack에 값 3 추가



Stack<Integer> stack = new Stack<>(); //int형 스택 선언

stack.push(1);     // stack에 값 1 추가

stack.push(2);     // stack에 값 2 추가

stack.push(3);     // stack에 값 3 추가

stack.pop();       // stack에 값 제거

stack.clear();     // stack의 전체 값 제거 (초기화)



Stack<Integer> stack = new Stack<>(); //int형 스택 선언

stack.push(1);     // stack에 값 1 추가

stack.push(2);     // stack에 값 2 추가

stack.push(3);     // stack에 값 3 추가

stack.peek();     // stack의 가장 상단의 값 출력



Stack<Integer> stack = new Stack<>(); //int형 스택 선언

stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가

stack.size();      // stack의 크기 출력 : 2

stack.empty();     // stack이 비어있는제 check (비어있다면 true)

stack.contains(1) // stack에 1이 있는지 check (있다면 true)
출처 : 
https://coding-factory.tistory.com/601
https://power-overwhelming.tistory.com/23
https://static.javatpoint.com/images/java-collection-hierarchy.png
https://blog.encrypted.gg/932

 

'Algorithm' 카테고리의 다른 글

이진 탐색 트리 자료구조  (1) 2023.03.28
트리  (0) 2023.03.27
해시 테이블 자료구조  (0) 2023.03.27
Queue 자료구조  (1) 2023.03.27
자료구조 정리  (0) 2023.03.24
'Algorithm' 카테고리의 다른 글
  • 트리
  • 해시 테이블 자료구조
  • Queue 자료구조
  • 자료구조 정리
JAVALA
JAVALA
워니‘s Diary
  • JAVALA
    정신줄 JAVA라
    JAVALA
  • 전체
    오늘
    어제
    • 분류 전체보기 (86) N
      • Codding_Test (11)
        • BaekJoon (7)
        • Programmers (3)
      • Algorithm (11)
      • Daily (4)
        • memoir (4)
      • TroubleShooting (8) N
        • InteliJ (1)
        • Server (1) N
        • Infra (0)
        • DB (0)
      • Computer Science (1)
      • JAVA (7)
      • Javascript (0)
      • Spring Boot (7)
      • API (2)
      • Server (0)
      • DB (3)
        • ORACLE (1)
      • Infra (2)
      • Refactoring (1)
      • Plugin (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    자바 스프링
    프론트엔드 개발자
    백엔드 개발자
    spring boot
    개발자
    자바 메소드
    백준
    트리 자료구조
    제로베이스
    개발자 국비
    자바 스프링부트
    자바
    자바 알고리즘
    프로그래머스
    코딩테스트
    개발자 부트캠프
    자바 클래스
    스프링부트
    springboot
    개발자 비전공자
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
JAVALA
List 자료구조
상단으로

티스토리툴바