ArrayList / LinkedList / Stack / Queue --- 구현하기

 

선형 자료구조 ( ArrayList / LinkedList / Stack / Queue )

---

 

ArrayList 구현하기

 

 

ArrayList 특징 

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 정해진 크기가 있음
• 요소의 추가와 제거 시 다른 요소들의 이동이 필요함
• 배열의 i 번째 요소를 찾는 인덱스 연산이 빠름
• jdk 클래스 : ArrayList, Vector

---

배열 구성

엘리먼트를 중간에 넣는 법

엘리먼트를 삭제하는 법 실습

 

 

배열 구성 - 배열 생성자 세팅과 배열에 추가 (add) 하는 메서드 생성  

 

 

---

 

자료 집어넣을 경우 - insertElement

- 넣을 수 있는 위치인지 확인 / 배열 꽉 찼는지 확인 / 가능하다면 맨 뒤부터 넣을 위치까지 뒤로 하나씩 미뤄주고 대입

 

 

---

 

자료 꺼내는 경우 - removeElement

- 꺼낼 수 있는 위치인지 확인 / 비어있는지 확인 / 가능하다면 꺼내고 빈자리 채워주기 

 

 

 

ArrayList 

 

배열 구성

- 디폴트 배열 size 생성자와 매개변수 사이즈 받아서 만드는 생성자 만들어주고, 배열에 추가하는 메서드 만들어줌

 

엘리먼트를 중간에 넣는 법 

 - 넣을 수 있는 위치인지 확인 / 배열 꽉 찼는지 확인 / 가능하다면 맨 뒤부터 넣을 위치까지 뒤로 하나씩 미뤄주고 대입

 

엘리먼트를 삭제하는 법 

 - 꺼낼 수 있는 위치인지 확인 / 비어있는지 확인 / 가능하다면 꺼내고 빈자리 채워주기

 

요소의 추가와 제거 시 다른 요소들의 이동이 필요함

---

 

 

연결 리스트 (LinkedList) 구현하기

 

LinkedList 특징

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가 될때 노드만큼의 메모리를 할당받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
• 연결 리스트의 i 번째 요소를 찾는 게 걸리는 시간은 요소의 개수에 비례 : O(n)
• jdk 클래스 : LinkedList

 

링크드 리스트에서

head 부분이 첫 번째 엘리먼트가 되는 경우와

head는 범위고 첫 번째 엘리먼트는 head 다음 엘리먼트인 경우

 

우리는 head = 첫 번째 엘리먼트 경우 실습

 

기본 노드 세팅 - 변수 생성 ( 자료 / 링크 ) , 상황 별 생성자 만들어주기 

---

 

데이터 추가 - 1. 데이터 맨 앞 / 맨 뒤 추가

 

 

 

---

 

데이터 추가 - 2. 중간에 추가하는 경우

0 - 1 - 2 - 3

 

넣을 때 - 2번 자리에 넣을 것이다. 하면 pre 노드 1번을 알아야 나를 가리키도록 할 수 있다.

 

 

---

 

데이터 삭제 -  중간에 삭제하는 경우

 

0 - 1 - 2 - 3

지울때 - 2번 자리 지울 것이다 하면 pre 노드 1번이 3번 가리키도록

 

 

---

 

출력 테스트 ---

 

 

 

 

링크드 리스트

 

변수와 상황별 생성자 세팅해주고

추가 부분 ( 맨 앞/맨뒤 , 중간 부분 ) 링크 변경 만들어주고

삭제 부분 링크 변경 만들어 주고

출력 TEST !

 

 

 

 

링크드 리스트가 내부적으로 이렇게 되어있는데

실제 라이브러리로 사용하는 것은 이렇게 간단하진 않다.

서큘러 더블 링크드 리스트

맨 마지막 노드가 다시 헤드를 가리키고 pre next 노드 서로 가리키는 것 있다.

가져다 쓰면 된다. 어떻게 돌아가는지 어떤 방식인지 이해 필요

 

---

 

 

스택(Stack) 구현하기

 

Stack의 특징

• 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내올 수 있음 ( 중간의 자료를 꺼낼 수 없음)
• Last In First Out ( 후입 선출 ) 구조
• 택배 상자가 쌓여있는 모양
• 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 부를 때 사용할 수 있음
• 함수의 메모리는 호출 순서에 따른 stack 구조
• jdk 클래스 : Stack

 

 

기본 스택 구성 - 

 

 

---

 

데이터 부분 - 추가해 줄 때 / 삭제할 때 / 꺼내볼 때 

 

 

+ 메서드 - 꽉 찼는지 확인할 때 사용한 메서드 / 비었는지 확인할 때 사용한 메서드

 

 

 

---

 

출력 테스트 ---

 

---

 

스택(stack)

 

맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내올 수 있음

top 위치를 기준으로 조건과 메서드들 핸들링.

 

 

---

 

 

큐(Queue) 구현하기

 

Queue의 특징

• 맨 앞(front)에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가함
• Fist In First Out (선입선출) 구조
• 일상생활에서 일렬로 줄 서 있는 모양
• 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용되는 자료구조
• 콜센터에 들어온 문의 전화, 메시지 큐 등에 활용됨
• jdk 클래스 : ArrayList

---

우리는 인터페이스 하나 선언해서 그것을 기반으로 만들어보기 

 

기본 세팅 - 구현할 interface 생성하고 ch03.어레이리스트 상속받기 

 

 

---

 

 

노드 추가 / 삭제 - 추가는 맨 앞, 삭제는 맨 뒤 - 이루어지도록 메서드 생성

 

 

---

출력 테스트 ---

 

 

큐 ( Queue )

front와 rear 추가는 맨 앞에서. 삭제는 맨 뒤에서 이루어진다.

 

 

---

 

 

review

배열(Array) / 링크드 리스트 / 스택 / 큐 를 직접 구현을 해보았다
.
배열 - 사이즈를 정해놓고 순서대로 들어가는 것이 큰 특징,
중간에 데이터 추가 시 - 뒤로 한 칸씩 다 미뤄준 다음에 그 자리에 추가 
중간에 데이터 삭제 시 - 삭제한 위치 기준 뒤에 데이터들 한 칸씩 당겨준다.

링크드 리스트 - 사이즈를 정해놓지 않아도 되고, 추가 순서대로 가 아닌 링크가 가리키는 순서로 구성
중간에 데이터 추가 시 - 전 노드가 나를 가리키게 하고, 전 노드가 가리키던 애를 내가 가리키도록 링크 변경 
중간에 데이터 삭제 시 - 나를 가리키고 있던 전 노드의 링크를 원래 내가 가리키고 있던 애를 가리키도록 변경

스택 - top 위치에서만 데이터의 추가와 삭제가 이루어진다.

큐 - 데이터의 추가는 front에서 삭제는 rear에서 이루어진다.

 정리해 놓으니 간단하네ㅎㅎ
구현 실습을 따라 해 보면서 구성은 이해하며 따라갔는데
상황에 맞게 배열을 조절하고, 링크를 수정하고 위치를 조절하는
조건과  원리들을 이해하는데 시간이 오래 걸렸다.
후후. 보통 실제 사용할 때는 라이브러리에서 가져와서 사용하는 거라
이런 조건들을 직접 코드 하는 일은 많지 않다고 하니 왜 이렇게 사용했는지 알아두면 될 것 같다.
코드 조건과 원리 보다도 자료 구조의 특징과 어떤 상황에 쓰면 좋을지를 알아두어야 할 것 같다.