선형자료구조 비교 - 앞뒤가 똑같은 전화번호 ..?
알고리즘 문제를 풀다가 헷갈리는 상황이 생겼습니다..
링크드 리스트, 큐, 데크 등의 선형 자료구조의 이미지를 떠올릴 때.. 어디가 앞이고 어디가 뒤인 거지?
(front) LIST (last) //..?
혹은
(last) LIST (front) // 어디가 front야..?
위 상황에서
보통 add()와 addLast()라는 메소드가 있으니까.. 두 메소드는 반대의 기능을 하는걸까...?
add-->> (front) LIST (last)
(front) LIST (last) <<-addLast
혹은
addLast-->> (last) LIST (front)
(last) LIST (front) <<--add라고 봐야하는 걸까?
한 번 링크드리스트에 직접 데이터를 넣고 자바가 어떠한 모양으로 출력해주는지 보았습니다.. (자바가 정해주는 게 앞이겠지..)
int[] arr = {1, 2, 3, 4, 5};
LinkedList<Integer> addLinkedList = new LinkedList<>();
LinkedList<Integer> addLastLinkedList = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
addLinkedList.add(arr[i]);
System.out.println(addLinkedList);
}
System.out.println("======================");
for (int i = 0; i < arr.length; i++) {
addLastLinkedList.addLast(arr[i]);
System.out.println(addLastLinkedList);
}
출력결과 :
출력결과를 보니
add()를 한 경우와
addLast()를 한 경우의 결과가 일치하였습니다.. 😇
그러다 순간 머릿속에서 번쩍이고 지나간 게 있었습니다..
아, front와 last의 관계가 아니라,,
front <-> rear
first <-> last 의 관점으로 봐야하는걸까?
역시나.. 찾아보니..
자자, 그럼 정리 !!
add()와 addLast()는 같은 기능을 하는 메소드이고 (rear 방향으로 삽입!)
addFirst()가 혼자 반대 기능을 하는 메소드이구나 ! (front 방향으로 삽입!)
addFirst -->> (front) LIST (rear)
(front) LIST (rear) <<- add & addLast
하지만 !!! remove()의 경우는 어떨까?
remove()와 removeFirst()가 같은 기능을 하는 메소드 ! (front 방향으로 poll! (..뽑기..?))
removeLast()가 혼자 반대 기능을 하는 메소드 !! (rear방향으로 poll)
remove & removeFirst <<- (front) LIST (rear)
(front) LIST (rear) --> removeLast
아 헷갈린다 헷갈려..
다음으로 선형 자료구조를 한 번 코드로 출력해보고 add, remove, pop을 해보겠습니다..!
Deque<Integer> deque = new ArrayDeque<>();
deque.add(1);
deque.add(2);
deque.addLast(3);
deque.addFirst(4);
System.out.println("DEQUE");
System.out.println(deque);
System.out.println("deque.remove() ==> " + deque.remove());
System.out.println(deque);
System.out.println("deque.removeFirst() ==> " + deque.removeFirst());
System.out.println(deque);
System.out.println("deque.removeLast() ==> " + deque.removeLast());
System.out.println(deque);
System.out.println("======================");
LinkedList<Integer> ll = new LinkedList();
ll.add(1);
ll.add(2);
ll.addLast(3);
ll.addFirst(4);
System.out.println("LINKED LIST");
System.out.println(ll);
System.out.println("ll.remove() ==> " + ll.remove());
System.out.println(ll);
System.out.println("ll.removeFirst() ==> " + ll.removeFirst());
System.out.println(ll);
System.out.println("ll.removeLast() ==> " + ll.removeLast());
System.out.println(ll);
System.out.println("======================");
System.out.println("ARRAY LIST");
ArrayList<Integer> al = new ArrayList<>();
al.add(1);
al.add(2);
al.add(3);
al.add(4);
// al.addLast(); 없음
// al.addFirst(); 없음
System.out.println(al);
System.out.println("al.remove(index or Object)");
System.out.println("======================");
System.out.println("STACK");
Stack<Integer> stk = new Stack<>();
stk.add(1);
stk.add(2);
stk.add(3);
stk.add(4);
// stk.addLast(); 없음
// stk.addFirst(); 없음
// 주의) 스택만 front <-> rear가 아닌 bottom <-> top
System.out.println(stk);
System.out.println("stk.pop() ===> " + stk.pop());
System.out.println(stk);
System.out.println("======================");
System.out.println("QUEUE");
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
// stk.addLast(); 없음
// stk.addFirst(); 없음
System.out.println(queue);
System.out.println("queue.remove() ===> " + queue.remove());
System.out.println(queue);
- 결과
DEQUE
[4, 1, 2, 3] //전체 출력
deque.remove() ==> 4
[1, 2, 3]
deque.removeFirst() ==> 1
[2, 3]
deque.removeLast() ==> 3
[2]
======================
LINKED LIST
[4, 1, 2, 3] //전체 출력
ll.remove() ==> 4
[1, 2, 3]
ll.removeFirst() ==> 1
[2, 3]
ll.removeLast() ==> 3
[2]
======================
ARRAY LIST
[1, 2, 3, 4] //전체 출력
al.remove(index or Object) //순서대로 뽑는 것이 아니라 타겟 지정해서
======================
STACK
[1, 2, 3, 4] //전체 출력 <<----- 스택만 (bottom) stk (top) 의 형태로 괄호 마지막 숫자가 pop !!
stk.pop() ===> 4
[1, 2, 3]
======================
QUEUE
[1, 2, 3, 4 //전체 출력
queue.remove() ===> 1
[2, 3, 4]
또한 sout 했을 때 출력 형태가
front) LIST (rear 이므로
항상 왼쪽 방향이 front라고 생각하는 게 좋을 것 같습니다..!
그러나.. 스택만은 구조가 좀 다르네요
1, 2, 3, 4 순서대로 push() 한 결과가
[ 1, 2, 3, 4]임을 볼 수 있는데, 왼쪽이 front인 다른 선형 자료구조들과는 달리,
왼쪽이 bottom, 오른쪽이 top 입니다!
pop()을 하면 오른쪽 top에서 값이 뽑는 것을 볼 수 있습니다..!
(bottom)[ 1, 2, 3, 4 ] (top)
[ 1, 2, 3 ] --> pop() : 4
물론 왼쪽, 오른쪽 이런 기준이
자료구조 정의로서의 절대적인 기준은 아니란 거 알고 계시죠? (메모리 상에서의 앞뒤란..?)
다만, 복잡한 코딩을 하면서 순간적으로 헷갈리지 않게
자바가 출력해주는 순서를 기준으로 나름의 정리를 하는데 의미를 두면 좋을 것 같습니다~
