Linkedlist의 자료구조를 직접 구현하기
연결리스트형태
-동적할당
package com.bit.day10;
//객체를 찍는 클래스 Node와 일을 수행하는 클래스 Linked
class Node{ //객체생성을 위한 클래스
int val;
Node next; //다음 객체의 주소저장
}
class Linked { //자료구조를 정의하는 클래스
Node startNode; //시작점 (참조변수)
int cnt;
void add(int a){ //값을 넣는 메소드
//step 1
Node node1=new Node(); //객체 찍음
node1.val=a; //찍은 객체에 add한 값을 준다.
startNode=node1; //새로생긴 객체의 주소를 기억시킨다.. = start만 알면 꼬리물기처럼 전 객체에 접근할 수 있다.
//step 2
Node node2=new Node();
node2.val=a;
startNode.next=node2; //startNode에 node1의 주소가 있으므로 node1객체의 next필드에 node2의 주소를 입력
//step 3
Node node3=new Node();
node3.val=a;
startNode.next=node3;
}
int get(int idx){ //값을 뽑아내는 메소드
//0. startNode.val; //node1객체의 value
//1. startNode.next.val;
//2. startNode.next.next.val;
int val=startNode.next.next.val; //node3의 value
return val;
}
}
public class Ex01 {
public static void main(String[] args) {
Linked list=new Linked();
list.add(1111); //add로 들어올때마다 객체를 찍고 값넣고
list.add(2222);
list.add(3333);
System.out.println(list.get(0));
}
}
package com.bit.day10;
//객체를 찍는 클래스 Node와 일을 수행하는 클래스 Linked
class Node{ //객체생성을 위한 클래스
int val;
Node next; //다음 객체의 주소저장
}
class Linked { //자료구조를 정의하는 클래스
Node startNode; //시작점 (참조변수) Node 타입이니까 필드에 접근 가능.
int cnt;
void add(int a){ //값을 넣는 메소드
cnt++;
Node temp=startNode;
Node node=new Node();
while(true){ //while문이 없으면 start에다가 node를 주는 동작이 된다. while문이 실행되면 start.next에 node를 주는것이다.
// startNode=startNode.next; //start는 무조건 시작노드를 가리키게 하고싶었으므로
temp=temp.next;
temp=temp.next; //temp.next에 next를 주는 것
}//cnt가 0이면 한번도 일어나지않도록, 1이면 한번만, 2이면 두번 일어나도록 만들고 싶음.
temp=node;
//step 1
Node node1=new Node(); //객체 찍음
node1.val=a; //찍은 객체에 add한 값을 준다.
startNode=node1; //새로생긴 객체의 주소를 기억시킨다.. = start만 알면 꼬리물기처럼 전 객체에 접근할 수 있다.
//step 2
Node node2=new Node();
node2.val=a;
startNode.next=node2;
//step 3
Node node3=new Node();
node3.val=a;
startNode.next=node3;
}
int get(int idx){ //값을 뽑아내는 메소드
//0. startNode.val;
//1. startNode.next.val;
//2. startNode.next.next.val;
int val=startNode.next.next.val; //node3의 value
return val;
}
}
public class Ex01 {
public static void main(String[] args) {
Linked list=new Linked();
list.add(1111); //add로 들어올때마다 객체를 찍고 값넣고
list.add(2222);
list.add(3333);
System.out.println(list.get(0));
}
}for문을 사용하면 몇번 반복할지를 고려해야하기 때문에 계산을 잘 해야 한다. 안돌아간다..
그래서 while문으로 돌렸다.
package com.bit.day10;
//객체를 찍는 클래스 Node와 일을 수행하는 클래스 Linked
class Node{
int val;
Node next;
}
class Linked {
Node startNode;
int cnt;
void add(int a){
cnt++;
// Node temp=startNode; 첫노드가 비어있으므로(주소가 없으므로) null 오류가 뜬다.
Node node=new Node();
node.val=a;
if(cnt==1){
startNode = node;
}else{
Node temp=startNode;
for(int i=2; i<cnt; i++){
temp=temp.next;
}
temp=node;
}
}
int get(int idx){
//0. startNode.val;
//1. startNode.next.val;
//2. startNode.next.next.val;
int val=startNode.next.next.val;
return val;
}
}
public class Ex01 {
public static void main(String[] args) {
Linked list=new Linked();
list.add(1111);
list.add(2222);
list.add(3333);
System.out.println(list.get(0));
}
}while문 = 몇번 반복할지 결정하지 않는 로직으로 구현했다.
Start의 next를 보고 안비어있으면 다음객체의 next를 본다. 비어있는 객체를 발견하면 거기에 새로생긴 객체의 주소를 준다.
package com.bit.day10;
//객체를 찍는 클래스 Node와 일을 수행하는 클래스 Linked
class Node{
int val;
Node next;
}
class Linked {
Node startNode;
int cnt;
void add(int a){
cnt++;
if(cnt==1){ //그래서 startNode에 첫 노드 node의 주소를 주었다.
Node node=new Node();
node.val=a;
startNode=node;
}else{
Node temp=startNode;
Node node=new Node();
node.val=a;
while(true){
if(temp.next==null){break;} //비어있으면 탈출한다.
temp=temp.next;
}
temp.next=node; //탈출하여 주소를 준다.
}
}
int get(int idx){
//0. startNode.val;
//1. startNode.next.val;
//2. startNode.next.next.val;
int val=startNode.next.next.val;
return val;
}
}
public class Ex01 {
public static void main(String[] args) {
Linked list=new Linked();
list.add(1111);
list.add(2222);
list.add(3333);
System.out.println(list.get(2));
}
}package com.bit.day10;
//객체를 찍는 클래스 Node와 일을 수행하는 클래스 Linked
class Node{
int val;
Node next;
}
class Linked {
private Node startNode;
private int cnt;
int size(){
return cnt; //cnt를 가져올순 있지만 값을 바꿀 순 없다.
}
void add(int a){
cnt++;
if(cnt==1){ //그래서 starNode에 첫 노드를 만들어 주소를 주었다.
Node node=new Node();
node.val=a;
startNode=node;
}else{
Node temp=startNode;
Node node=new Node();
node.val=a;
while(true){
if(temp.next==null){break;} //비어있으면 탈출한다.
temp=temp.next;
}
temp.next=node; //탈출하여 주소를 준다.
}
}
int get(int idx){
//0. startNode.val;
//1. startNode.next.val;
//2. startNode.next.next.val;
int su=0;
Node temp=startNode;
for(int i=0; i<idx; i++){ //0일땐 한번도 안하도록. 1일때 한번
temp=temp.next;
}
su=temp.val;
return su;
}
}
public class Ex01 {
public static void main(String[] args) {
Linked list=new Linked();
list.add(1111);
list.add(2222);
list.add(3333);
list.add(4444);
list.add(5555);
for(int i=0; i<list.size(); i++){
System.out.println(list.get(i));
}
}
}java.util.LinkedList list=new java.util.LinkedList();
