* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.
5장부터는 구조체 개념이 나온다.
구조체는 여러 데이터를 하나로 묶은 것인데, 구조체 기반의 배열도 만들 수 있다.
구조체를 활용해서 연결 리스트를 구현 할 수 있는데 (= 리스트)
배열의 한 요소가 어디에 연결되어있는지에 관한 정보를 가지고 있다.
자바에서는 레퍼런스 개념임!
연결 리스트를 사용하면 요소의 물리적 순서와 관계없이 연결 정보로 요소의 논리적 순서를 결정한다.
연결 리스트는 그냥 배열과 달리 요소의 삽입 / 제거가 효율적이다.
만약에
서울 - 천안아산 - 대전 - 동대구 - 부산 이라는 연결 리스트가 있을 때 ,
서울 뒤에 광명을 끼우려면 원래 배열은 한칸씩 다 >> 를 해줘야 함.
근데 연결 리스트는 그냥 연결 정보값만 수정하면 됨.
서울 - 천안아산 - 대전 - 동대구 - 부산 - 광명
순서로 삽입했었어도,
head(실제 논리적 순서의 시작점) 가 서울일 때, head가 가리키는 것을 광명으로 하면 됨.
삭제 시에도 하나 지우고 배열은 한 칸씩 다 << 를 해줘야 하는데,
연결 리스트는 그냥 연결 정보를 가리키던 값들을 수정해 주면 끝임.
이게 배열보다 좋은 것 같지만, 사실 요소 가져올 때 처리가 생각보다 많이 필요해서
단점도 있음.
연결 리스트에서는 만약에 세번째 위치한 값을 가져오려면 이렇게 해야 함.
1) head를 참조해서 첫 번째 요소가 a[2] 임을 확인함
2) a[2] 를 참조하여 논리적 순서의 두 번쨰 요소가 a[4] 임을 확인함
3) a[4] 를 참조하여 세 번째 요소가 a[1]이고, 요소값이 대전임을 확인함
이런 식으로 논리적인 순서를 다 타야 하기 떄문에 요소 검색 시에는 시간이 많이 걸린다.
사실 자바는 그냥 연결 리스트를 LinkedList list = new LinkedList(); 로 선언하면 만들 수 있긴 한데, 공부를 위해서 직접 만든다고 한다.
(주의) 공부용이라 C 비슷하게 예제가 나왔다고 한다.
생성자도 안 쓰고, 접근 제어도 public으로 해버림!
* 찐으로 구현할 때는 이렇게 하지 말 것.
list랑 head는 함수 외부에서 선언해서 사용한다고 한다.
이걸 의사 코드로 만들어 보면 아래와 같다.
이걸 코드로 짜면 아래와 같다.
class StationList{
public String name; //역이름
public int next; //연결 정보
}
public class 연결리스트 {
public static StationList [] list = new StationList[10];
public static int head;
public static void main(String[] args) {
initStationList();
printStationList();
}
public static void initStationList(){
for(int i = 0; i< list.length; i++){
list[i] = new StationList();
}
list[0].name = "부산";
list[0].next = -1;
list[1].name = "대전";
list[1].next = 3;
list[2].name = "서울";
list[2].next = 4;
list[3].name = "동대구";
list[3].next = 0;
list[4].name = "천안아산";
list[4].next = 1;
head = 2; //서울을 head로 설정함
}
public static void printStationList(){
int idx = head;
while (idx != -1){
//-1인 부산을 맨 마지막으로
System.out.println(idx + " 는 " + list[idx].name);
idx = list[idx].next;
}
}
}
insertStationList 를 의사코드로 작성하면 아래와 같다.
자바로 구현하면 아래와 같다.
class StationList{
public String name; //역이름
public int next; //연결 정보
}
public class 연결리스트_추가 {
public static StationList [] list = new StationList[10];
public static int head;
public static void main(String[] args) {
initStationList_();
printStationList();
System.out.println("---------------------------");
initStationList(5, "광명", 2);
printStationList();
}
public static void initStationList_(){
for(int i = 0; i< list.length; i++){
list[i] = new StationList();
}
list[0].name = "부산";
list[0].next = -1;
list[1].name = "대전";
list[1].next = 3;
list[2].name = "서울";
list[2].next = 4;
list[3].name = "동대구";
list[3].next = 0;
list[4].name = "천안아산";
list[4].next = 1;
head = 2; //서울을 head로 설정함
}
public static void initStationList(int insIdx, String insName, int prevIdx){
list[insIdx].name = insName;
list[insIdx].next = list[prevIdx].next; //앞 연결 요소 설정
list[prevIdx].next = insIdx;
}
public static void printStationList(){
int idx = head;
while (idx != -1){
//-1인 부산을 맨 마지막으로
System.out.println(idx + " 는 " + list[idx].name);
idx = list[idx].next;
}
}
}
이렇게 광명을 껴넣을 수 있다.
위치는 list[5] 인데 2 뒤에 넣어야 하니까 서울 뒤에 들어감
이렇게 만든 상태에서 요소를 삭제도 가능한데, 의사 코드는 아래와 같다.
삭제 시 필요한 것은 삭제할 요소의 인덱스, 삭제할 요소의 하나 앞 요소 인덱스이다.
구현하면 아래와 같다.
class StationList{
public String name; //역이름
public int next; //연결 정보
}
public class 연결리스트_추가 {
public static StationList [] list = new StationList[10];
public static int head;
public static void main(String[] args) {
initStationList_();
printStationList();
System.out.println("---------------------------");
initStationList(5, "광명", 2);
printStationList();
System.out.println("---------------------------");
deleteStationList(5, 2);
printStationList();
}
private static void deleteStationList(int delIdx, int prevIdx) {
list[prevIdx].next = list[delIdx].next;
//삭제할 요소의 하나 앞 인덱스를 현재 삭제할 요소의 인덱스로 바꿔준다.
// 그러면 삭제할 요소는 연결 리스트에서 빠짐
}
public static void initStationList_(){
for(int i = 0; i< list.length; i++){
list[i] = new StationList();
}
list[0].name = "부산";
list[0].next = -1;
list[1].name = "대전";
list[1].next = 3;
list[2].name = "서울";
list[2].next = 4;
list[3].name = "동대구";
list[3].next = 0;
list[4].name = "천안아산";
list[4].next = 1;
head = 2; //서울을 head로 설정함
}
public static void initStationList(int insIdx, String insName, int prevIdx){
list[insIdx].name = insName;
list[insIdx].next = list[prevIdx].next; //앞 연결 요소 설정
list[prevIdx].next = insIdx;
}
public static void printStationList(){
int idx = head;
while (idx != -1){
//-1인 부산을 맨 마지막으로
System.out.println(idx + " 는 " + list[idx].name);
idx = list[idx].next;
}
}
}
이러하다!
이건 사실 단방향 연결 리스튼데, 양방향도 있고 뭐 원형도 있고 그러하다...
양방향 : 앞/뒤 정보 가지고 있음
원형 : head가 tail을 가리키는 구조라 한바퀴 돌고 있음
* 사실 개념상 알아두고 자바는 그냥 LinkedList를 쓰자...
(공부용으로는 코딩 테스트 연습용 풀 때 복기 목적으로 가끔 짜 보면 좋음)
댓글
댓글 쓰기