List 자료구조

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

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

데이터 적재라는 새로운 장점을 취한 자료구조
- 중복된 데이터의 저장 허용
- 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