linkedlist : 순서를 가지도록 데이터를 나열한 것
-
Node 에는 data, next가 저장되어있고 또 next에는 Node라는 객체가 저장되어있고 그 Node에는 data, next가 저장되어있음...
-
생성자 = 메소드
- 리스트란?
순서를 가지도록 데이터를 나열한 것
리스트에서는 각각의 요소를 노드라고 한다.
노드는 데이터와 다음 노드로 구성되어 있다.
head 맨 처음 노드
current 현재 노드(검색같은거할때필요함)- 리스트의 구현(무조건 냅다 클래스부터만들기)
노드 클래스도 만든다.
리스트 클래스부터 만든다.(LinkedList)
1) 노드 클래스
데이터와 노드를 저장할 수 있는 클래스
- Node 에는 data, next가 저장되어있고 또 next에는 Node라는 객체가 저장되어있고 그 Node에는 data, next가 저장되어있음...
2) 리스트 클래스
head 맨 처음 노드 -> Node head;
package list;
public class LinkedList {
private Node head;
// (0) 생성자 head에 null 저장
LinkedList() {
this.head = null;
}
// (1) display head에서부터 data를 출력하고 next 출력 next 출력 next
public void display() {
Node node = head;
while(node != null) {
System.out.print("[" + node.data + "]");
node = node.next;
}
System.out.println();
}
// (2) insertFirst -> 메소드로 만들어서 데이터 하나를 전달 받는다.
// 노드 객체 생성
// 방금 생성한 노드의 next에 기존 head 저장
// head에 방금 생성한 노드 저장
public void insertFirst(Integer data) {
Node newNode = new Node(data, null);
newNode.next = head;
head = newNode;
}
// (2) insertLast -> 생성자만들고 매개변수로 Integer data
// 데이터 하나를 전달 받는다. -> 매개변수로!
// 만약에 head가 null 이면
// insertFirst 실행
// 그렇지 않으면
// 노드를 저장할 수 있는 변수1 생성
// 변수1에 head 저장
// 변수1의 next가 null이 아니면 반복
// 변수1에 변수1의 next를 저장
// 노드를 저장할 수 있는 변수2 생성
// 변수2에 노드 객체를 생성해서 저장
// 변수1의 next에 변수2 저장
public void insertLast(Integer data) {
if(head == null) {
this.insertFirst(data);
} else {
Node node;
node = head;
while(node.next != null) {
node = node.next;
}
Node newNode;
newNode = new Node(data, null);
node.next = newNode;
}
}
// (3) insertIndex
// 원하는 순서에 데이터를 추가하는 기능
// 데이터 하나를 전달 받는다.
// 순서번호를 하나 전달받는다.
//
//
// 만약에 head가 null 이거나 순서번호가 0이면 -> 이거나 ||
// insertFirst 실행
// 그렇지 않으면
// 노드를 저장할 수 있는 변수1 생성
// 변수1에 head 저장
// 숫자를 저장할 수 있는 변수2 생성
// 변수2에 0 저장
// 변수2가 순서번호 -1 이랑 다르면 반복
// 변수1에 변수1의 next를 저장
// 변수2에 값1 증가해서 저장
// 노드를 저장할 수 있는 변수3 생성
// 변수3에 노드 객체를 생성해서 저장
// 변수3의 next에 변수1의 next를 저장
// 변수1의 next에 변수3 저장
public void insertIndex(Integer index, Integer data) {
if(head == null || index==0) {
this.insertFirst(data);
} else {
Node node;
node = head;
Integer count;
count = 0;
while(count != index - 1) {
node = node.next;
count = count + 1;
}
Node newNode;
newNode = new Node(data, null);
newNode.next = node.next;
node.next = newNode;
}
}
// (4) removeFirst -> 삭제는 전달받을게없으니까 void
// 맨 처음 노드를 삭제하는 기능
//
// 만약에 head가 null이 아니면
//
// 노드를 저장할 수 있는 변수1 생성
// 변수1에 head의 next를 저장
// head.next에 null 저장
// head에 변수1 저장
public void removeFirst() {
if(head != null) {
Node secondNode;
secondNode = head.next;
head.next = null; // 첫번째 노드에서 두번째노드로 연결되는걸 끊음
head = secondNode; // 두번째노드를 헤드로 만들어서 첫번째 노드는 삭제되게 함
}
}
// (5) removeLast
// 맨 마지막 노드를 삭제하는 기능
//
// 만약에 head가 null이 아니면
// 노드를 저장할 수 있는 변수1 생성
// 변수1에 head 저장
// 노드를 저장할 수 있는 변수2 생성
// 변수2에 null 저장
// 변수1의 next가 null이 아니면 반복
// 변수2에 변수1 저장
// 변수1에 변수1의 next 저장
// 변수2의 next에 null 저장 -> 마지막거와 연결을 끊겠다~
public void removeLast() {
if(head != null) {
Node node;
node = head;
Node preNode;
preNode = null;
while(node.next != null) {
preNode = node;
node = node.next;
}
preNode.next = null;
}
}
// (6) removeIndex
// 원하는 순서의 노드를 삭제하는 기능
//
//
// 만약에 head가 null이 아니면
// 노드를 저장할 수 있는 변수1 생성
// 변수1에 head 저장
// 숫자를 저장할 수 있는 변수2 생성
// 변수2에 0 저장
// 노드를 저장할 수 있는 변수3 생성
// 변수3에 null 저장
// 변수2가 순서번호랑 다르면 반복 -> 처음부터 index까지 next하는 것
// 변수3에 변수1 저장
// 변수1에 변수1의 next 저장
// 변수2에 변수2 + 1 저장
// 변수3의 next에 변수1의 next 저장
// 변수1의 next에 null 저장
public void removeIndex(Integer index) {
if(index == 0) {
removeFirst();
} else if(head != null) {
Node node;
node = head;
Integer count;
count = 0;
Node preNode;
preNode = null;
while(count != index) {
preNode = node;
node = node.next;
count = count + 1;
}
preNode.next = node.next;
node.next = null;
}
}
}
tree : 계층을 가지도록 데이터를 나열한 것
- 이진탐색트리 : 데이터를 저장할 때 큰 걸 오른쪽에, 작은 걸 왼쪽에 저장
트리의 루트 노드 : 가장 윗부분에 있는 노드
트리의 리프 노드 : 가장 밑부분에 있는 자식이 없는 노드들
부모 : 특정 노드의 상위 노드
자식 : 특정 노드의 하위 노드
형제 : 부모가 같은 노드
조상 : 부모의 부모의 부모의 부모의 ....... 까지
자손 : 자식의 자식의 자식의 자식의 ....... 까지
레벨 : 루트로부터 얼마나 떨어져 있는가
차수 : 자식 노드의 수
트리의 높이 : 루트에서 제일 먼 리프까지의 거리
이진트리 : 최대 차수가 2인 트리
삼진트리 : 최대 차수가 3인 트리
사진트리 : 최대 차수가 4인 트리
