publicstaticvoidbigNumber()throws Exception { BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String s = in.readLine();
String[] A = s.split(" "); if (n != A.length) { return; }
int[] NGE = newint[n]; Stack<Integer> stack = new Stack<>();
stack.push(0); for (int i = 1; i < n; i++) { int a = Integer.parseInt(A[i]); while (!stack.isEmpty() && Integer.parseInt(A[stack.peek()]) < a) { NGE[stack.pop()] = a; } stack.push(i); }
while (!stack.isEmpty()) { NGE[stack.pop()] = -1; }
for (int ans : NGE) { out.write(ans + " "); } out.write("\n"); out.flush(); out.close(); in.close(); } }
Posted onInComputer
,
CodingTestDisqus: Symbols count in article: 1.8kReading time ≈2 mins.
쇠막대기
문제
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
입력
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.
출력
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
예제 입력 1
1
()(((()())(())()))(())
예제 출력 1
1
17
예제 입력 2
1
(((()(()()))(())()))(()())
예제 출력 2
1
24
풀이
스택을 이용하여 문제를 해결할 수 있다. () 은 레이저이고, ( 의 시작하여 ) 끝은 쇠막대기를 열고 닫는 괄호이며, 쇠막대기 사이에는 () 들이 있다.
ex) (((()())(())()))
( 가 열릴 때마다 스택에 담는다
) 가 닫히면 제일 가까이 있는 (를 꺼낸다.
만약 이전 괄호가 ) 일 경우 1개만 증가하고(쇠막대기 1개를 레이저가 3번 자르면 쇠막대기는 4조각으로 나눠지기 때문에…) 그렇지않으면 스택의 사이즈 만큼 증가한다 result += (before == ')') ? 1 :stack.size();
publicstaticvoidironBar()throws Exception { BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine(); int result = 0; char before = ' '; Stack<Character> stack = new Stack<>(); for (char ch : s.toCharArray()) { switch (ch) { case'(': stack.push(ch); break; case')': stack.pop(); result += (before == ')') ? 1 :stack.size(); break; } before = ch; } out.write(result + "\n"); out.flush(); out.close();; in.close(); } }
Posted onInComputer
,
CodingTestDisqus: Symbols count in article: 2.3kReading time ≈2 mins.
단어뒤집기 2(Word Flipping 2)
문제
문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.
먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.
알파벳 소문자(‘a’-‘z’), 숫자(‘0’-‘9’), 공백(‘ ‘), 특수 문자(‘<’, ‘>’)로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ‘<’와 ‘>’가 문자열에 있는 경우 번갈아가면서 등장하며, ‘<’이 먼저 등장한다. 또, 두 문자의 개수는 같다. 태그는 ‘<’로 시작해서 ‘>’로 끝나는 길이가 3 이상인 부분 문자열이고, ‘<’와 ‘>’ 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.
publicstaticvoidreplace()throws Exception { BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine();
boolean tag = false; Stack<Character> stack = new Stack<>();
get firstElem() { returnthis._arr.length ? this._arr[0] : null; } set firstElem(elem) { this._arr = [elem, ...this._arr]; //... this._arr은 this._arr을 개별 요소로 분리 } }
const foo = new Foo([1,2,3,4,5]);
foo.firstElem = 100; //set 키워드를 사용한 메서드로 데이터를 할당 할 때 필드명을 사용.
console.log(foo.firstElem); //get 키워드를 사용한 메서드를 불러올 때 필드명을 가져올 때처럼 사용
정적 메서드 (static method)
정적 메서드를 정의 하려면 static 키워드를 사용하면 된다. 정적 메서드는 클래스의 인스턴스가 아닌 클래스 이름으로 호출한다. 그래서 클래스의 인스턴스를 생성하지 않아도 호출할 수 있다.
정적 메서드는 this를 사용할 수 없으며, 정적 메서드 내부에서 클래스 인스턴스를 가리키는 것이 아니라 자기 자신을 기리킨다.
classPerson{ constructor(age) { this._age = age; } static staticMethod() { /** 정적 메서드는 this를 사용할 수 없으며, 정적 메서드 내부에서 클래스 인스턴스를 가리키는 것이 아니라 자기 자신을 기리킨다. **/ return'staticMethod age: ' + this._age; }
prototypeMethod() { returnthis._age } } //정적 메서드는 클래스 이름을 호출 console.log(Person.staticMethod()); //staticMethod age: undefined
const me = new Person(34);
//정적 메서드는 인스턴스로 호출할 수 없다. console.log(me.staticMethod()); //Uncaught TypeError: me.staticMethod is not a function
클래스도 function이고 기존 prototype 기반 패턴의 Syntatic suger일 뿐이다.
var me = new Person(34); console.log(me.prototypeMethod()); //34 console.log(Person.staticMethod()); //staticMethod age: undefined console.log(me.staticMethod());//Uncaught TypeError: me.staticMethod is not a function console.log(Person.prototype === me.__proto__); // true console.log(Person.prototype.constructor === Person); //true
클래스 상속(Class Inheritance)
클래스 상속은 새롭게 정의할 클래스가 기존 클래스와 유사할 경우 상속을 통해 그대로 사용하고 다른 점만 구현할 수 있다. 즉 하위 클래스에서 상속받아 상위 클래스의 정보를 다시 재사용할 수 있는 것이다. 코드의 재사용할 경우 개발 비용을 줄일 수 있다.
get getAge() { returnthis.age; } set setAge(age) { returnthis.age = age; } getInfo() { return'My name is ' + this.name + 'and age is ' + this.age; } }
const child = new Child('hello', 33); console.log(child.getInfo()); //My name is helloand age is 33 child.setAge = 20; console.log(child.getAge); 20 console.log(child.getInfo()); //My name is helloand age is 20 child.setName = 'World'; console.log(child.getName); //World
get getAge() { returnthis.age; } set setAge(age) { returnthis.age = age; } getInfo() { return'My name is ' + super.getName + ' and age is ' + this.age; //super를 통해 getName 참조 } }
const child = new Child('hello', 33); console.log(child.getInfo()); //My name is hello and age is 33 child.setAge = 20; console.log(child.getAge); 20 console.log(child.getInfo()); //My name is hello and age is 20 child.setName = 'World'; console.log(child.getName); //World
super 메서드는 자식 클래스의 생성자 내부에서 부모 클래스 생성자(슈퍼클래스)를 호출한다. 즉 부모 클래스의 인스턴스를 생성한다. 그래서 자식 클래스의 생성자에서 super()를 호출하지 않으면 this에 대한 참조 에러(ReferenceError)가 발생한다.
1 2 3 4 5 6 7 8 9
classParents{}
classChildextendsParents{ constructor() {
} }
const child = new Child(); //Uncaught ReferenceError: Must call super constructor in derived class before accessing 'this' or returning from derived constructor
Arrows 함수는 function 키워드 대신 화살표(‘=>’) 를 사용하여 함수를 선언하는 축약형 함수이다. Arrows는 표현식 본문(Expression Bodies)와 상태 블럭 본문(Statement block bodies)를 지원한다.
콜백 함수에서 사용하면 간결하게 표현이 가능.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
//매개변수 지정 방법 () => {...} // 매개변수가 없는 경우 x => {...} // 매개변수가 한 개인 경우, 소괄호를 생략할 수 있다. (x,y) => {...} //매개변수가 여러 개의 경우, 소괄호를 생략할 수 없다.
//함수 몸체의 지정 방법 x => { return x * x} //signle line block x => x * x //함수의 몸체가 한줄구문이라면 중괄호를 생략할 수 있고 암묵적인 리턴이 된다. () => { return { a:1 }; } () -> ({a:1}) //위 표현과 동일하고 객체 반환시 소괄호를 사용한다.
//Multi line Block () => { const x = 10; return x * x; }
화살표 함수는 익명함수로만 사용할 수 있다. 화살표를 호출 하기 위해서는 함수 호출 식을 사용한다.
1 2 3 4 5 6 7
//ES6 var pow = function(x) { return x * x }; console.log(pow(10)); //100;
//ES6 const pow = x => x * x; console.log(pow(10)); //100;
콜백함수로도 사용할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12
//ES5 var arr [1,2,3]; var pow = arr.map(function(x) { return x * x; }); console.log(pow); //[1, 4, 9]
생성자 함수는 prototype 프로퍼티를 가지며 prototype 프로퍼티가 가리키는 프로토타입 객체의 constructor를 사용한다. 그러나 화살표 함수는 prototype 프로퍼티를 가지고 있지 않다.
addEventListener 함수의 콜백 함수
addEventListener 함수의 콜백함수를 화살표로 정의 하면 this가 상위 컨택스트인 전역객체 window를 가리킨다. 그래서 function 키워드로 정의한 일반함수를 사용해야 하며, 이런 일반함수로 정의된 addEventListener 함수의 콜백 내부 this는 이벤트 리스너의 바인딩 요소를 가리킨다.
Posted onEdited onInComputer
,
CodingTestDisqus: Symbols count in article: 1.6kReading time ≈1 mins.
[BaekJoon-1158] 요세푸스 문제(Josephus of problem)
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
1
7 3
예제 출력 1
1
<3, 6, 2, 7, 5, 1, 4>
풀이
큐를 이용하여 문제를 해결 할 수 있다.
N 이 7 이고 K 가 3 일 경우
K번 째가 되기 전 까지 맨 앞 데이터를 꺼내어(poll) 다시 queue에 맨 뒤에 삽입(offer) 한다.
K 번째가 되었을 때 맨 앞 데이터를 꺼내어(poll) list에 담거나, 문자열에 담는다.
publicstaticvoidjosephus()throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = in.readLine().split(" "); int n = Integer.parseInt(input[0]); int k = Integer.parseInt(input[1]);
Queue<Integer> queue = new LinkedList<>(); List<Integer> result = new ArrayList<>();
for (int i = 1; i <=n; i++) { queue.offer(i); } int cnt = 1; StringBuilder sb = new StringBuilder("<"); while (!queue.isEmpty()) { if (k == cnt) { cnt = 1; sb.append(queue.poll()); if (!queue.isEmpty()) { sb.append(", "); } } else { cnt++; queue.offer(queue.poll()); } } sb.append(">"); out.write(""+ sb.toString()); out.flush(); out.close(); in.close(); } }
Posted onEdited onInComputer
,
CodingTestDisqus: Symbols count in article: 3.6kReading time ≈3 mins.
[BaekJoon-1406] 에디터(Editor)
문제
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L
커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D
커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B
커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $
$라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.
출력
첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.
예제 입력 1
1 2 3 4 5
abcd 3 P x L P y
예제 출력 1
1
abcdyx
예제 입력 2
1 2 3 4 5 6 7 8 9 10 11
abc 9 L L L L L P x L B P y
예제 출력 2
1
yxabc
예제 입력 3
1 2 3 4 5 6 7 8 9 10 11 12 13
dmih 11 B B P x L B B B P y D D P z
예제 출력 3
1
yxz
풀이
커서(cursor : |)를 기준으로 왼쪽 스택(left) 오른쪽 스택(right)로 나누어서 문제를 해결할 수 있다.
스택을 2개 만들고 문자열을 left에 초기화로 넣고 문제를 해결해 나가면 된다.
L 일 경우 왼쪽 스택 데이터를 Pop 하여 오른쪽 스택으로 Push 한다.
D 일 경우 오른족 스택 데이터를 Pop 하여 왼쪽으로 움긴다.
B 일 경우 왼쪽에 있는 스택 데이터를 하나 삭제(Pop)한다.
P $ 일 경우 $를 스택 왼쪽에 추가(Push) 하면된다.
알고리즘 분류를 보면 연결리스트라고 되어 있는데 연결리스트를 통해 문제를 풀면 시간초과로 Fail이 되버린다.
publicstaticvoideditorLinkedList()throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String read = in.readLine(); if (read.length() > 100000) { return; } int m = Integer.parseInt(in.readLine());
if (m < 1 || m > 500000) { return; }
List<Character> list = new LinkedList<>(); for (char ch : read.toCharArray()) list.add(ch);
publicstaticvoideditor()throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String read = in.readLine(); if (read.length() > 100000) { return; } int m = Integer.parseInt(in.readLine());
if (m < 1 || m > 500000) { return; }
Stack<Character> left = new Stack<>(); Stack<Character> right = new Stack<>(); for (char ch : read.toCharArray()) left.push(ch);
for (int i = 0; i < m; i++) { String input = in.readLine(); switch (input.charAt(0)) { case'L': if (!left.isEmpty()) right.push(left.pop()); break; case'D': if (!right.isEmpty()) left.push(right.pop()); break; case'B': if (!left.isEmpty()) left.pop(); break; case'P': left.push(input.charAt(2)); break;
} }
while (!left.isEmpty()) { right.push(left.pop()); } while (!right.isEmpty()) { out.write("" + right.pop()); } out.flush();
Posted onInComputer
,
CodingTestDisqus: Symbols count in article: 2kReading time ≈2 mins.
[BaekJoon-1874] 스택수열(Stack Sequence)
문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
예제 입력 1
1 2 3 4 5 6 7 8 9
8 4 3 6 8 7 5 2 1
예제 출력 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
+ + + + - - + + - + + - - - - -
예제 입력 2
1 2 3 4 5 6
5 1 2 5 3 4
예제 출력 2
1
NO
힌트
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
풀이
1부터 N까지의 수를 스택에 넣었다가 뽑음으로 하나의 수열을 만듬
push 순서 오르차순
임의 수열이 주어졌을 때 풀 수 있는지 없는지 있을 경우 Push (+) pop(-) // 풀수없을 경우 NO 출력
예제입력 seq = [4, 3, 6, 8, 7, 5, 2, 1] 가 주어 졌을 때 출력 + + + + - - + + - + + - - - - - 이 된다.
일단 1부터 N까지의 순차적으로 루프를 돌며 seq[i] 번째 데이터와 일치할 때 가지 루프를 돌며 스택에 데이터를 push한다.
publicstaticvoidstackSequence()throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(in.readLine()); int[] seq = newint[n]; for (int i = 0; i < n; i++) { seq[i] = Integer.parseInt(in.readLine()); }
Stack<Integer> stack = new Stack<>(); StringBuilder sb = new StringBuilder(); int m = 0; for (int data : seq) { if (m < data) { while (m < data) { stack.push(++m); sb.append("+\n"); } stack.pop(); sb.append("-\n"); } else { if (stack.peek() != data) { System.out.println("NO"); return; } stack.pop(); sb.append("-\n"); } }
@Override publicvoidenqueue(T data){ if (isFull()) { thrownew IndexOutOfBoundsException("queue is Full..."); } int rear = (this.rear) % this.capacity; queue[rear] = data; this.rear = rear+ 1; this.length++; System.out.println("enqueue : rear : "+ rear +" front : "+ front); }
@Override public T dequeue(){ if (isEmpty()) { thrownew IndexOutOfBoundsException("queue is empty..."); } int front = ((this.front) % this.capacity); Object data = queue[front]; queue[front] = null; this.front = front + 1; this.length--; System.out.println("dequeue : rear : "+ rear +" front : "+ front); return (T)data; }
Posted onInComputer
,
AlgorithmDisqus: Symbols count in article: 19kReading time ≈17 mins.
연결리스트(Linked List)
개념과 구조
데이터가 연속적인 리스트
새로운 노드를 삽입하거나 삭제가 간편
링크라는 개념을 통해 물리 메모리를 연속적으로 사용하지 않아도 된다.
데이터를 구조체로 묶어 포인터로 연결
Linked List에는 기본적으로 Node와 Link라는 용어를 사용
HeadNode에는 데이터를 저장하지 않는다. 단지 LinkedList의 시작부분임을 나타낸다.(ex:기관차에서 headNode는 승객이 타지 않음)
LinkedList의 마지막 부분을 나타내는 노드도 있다. End Node or Tail Node라고 불리며, 데이터를 저장하지 않는다. 즉, Head, Tail(End) 노드는 데이터를 저장하지 않음(저장할 수 없다는 것이 아니라 묵시적으로 데이터를 저장하지 않는다는 것)
링크에 화살표가 표시되어 있는 방향은 Head Node 부터 시작해 연결된 다음 노드들을 계속 가리키다보면 D에는 EndNode를 가리키고 EndNode는 아무것도 가리키지 않는 상태가 된다. 이와 같이 자신의 노드에서 다음 노드만 가리킬 수 있는 형태가 전형적이 LinkedList 의 형태이다.
연결리스트의 구조체
c
1 2 3 4
typedef struct _Node { char data; //데이터 struct _Node *next; //다음노드 꼬리 Link } Node;
@Override public T get(int index){ if (header == null && length == 0) { thrownew IndexOutOfBoundsException(); } Node cur = header; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.data; }
@Override publicintsize(){ returnthis.length; }
@Override public T getLast(){ return get(length); }
@Override public T get(int index){ if (header == null && length == 0) { thrownew IndexOutOfBoundsException(); } T data = null; if (index == 0) { data = getFirst(); } elseif (index == length - 1) { data = getLast(); } else { Node cur = header; for (int i = 0; i < index; i++) { cur = cur.next; } } return data; }
@Override publicintsize(){ returnthis.length; }
@Override public T getLast(){ return header.prev.data; }
@Override public T getFirst(){ return header.next.data; }
@Override public T get(int index){ if (header == null && length == 0) { thrownew IndexOutOfBoundsException(); } Node cur = header; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.data; }
@Override publicintsize(){ returnthis.length; }
@Override public T getLast(){ return get(length); }
