잡담
최근 CS 기초 지식을 공부하다보니, 내가 기초 기본지식에 너무 무지하지않은가? 라는 생각이 들었다. 아무래도 회사를 다니면서 취업준비를 하다보니, 시간적인 여유가 생기지 않아 힘들지만, CS 기초는 중요하게 여긴다하여, 따로 시간을 내어 공부중이다.
일단 내 공부방법대로 Linked list 자료의 역사에 대해 알아보자!!🧑🏻💻
Linked List의 등장배경
연결리스트는 배열의 메모리 공간의 비효율적인 사용을 커버하기 위해 나온 자료구조이다. 우리가 배열을 생각해봤을때, 메모리에 4Byte 크기의 10개 공간을 확보했다고 해보자
int[] Size4_10 = new int[10];
Size4_10 = {1...10}근데 우리가 메모리 공간상에 10개의 정수형 변수들을 대입하면, 10개의 공간을 효율적으로 사용하는 것이다. 근데 특정 로직에 의해, 9개의 수를 담게 되었다고 해보자, 즉 1개의 공간이 비게 된것이다. 그렇담 이것은 메모리 공간의 낭비이지 않은가?
이러한 공간 낭비를 줄이기 위해, Node 간의 연결 상태를 확립하고, 해당 값을 제외해야 한다면, 연결을 끊고, 메모리 상에서 그 끊은 노드의 Next Node 와 연동시켜준뒤, 제거하자! 그럼 메모리 상에 공간 낭비는 없지 않은가? 라는 발상으로 등장한 자료구조입니다.
구현해야 할것
-
Node 는 하나의 값을 가진 객체를 말하며, Head 와 Tail 에 NextNode 와 PreviousNode 의 메모리 주소값 정보를 가지고 있다.
-
NodeA <-> NodeB <-> NodeC 가 연결되어 있었다면 Node B가 연결을 끊으면, NodeA 와 NodeC 사이의 연결을 확립시켜줘야됨
구현 중심 기능 Flow
-
삭제시 연결 확립 후 Data 를 삭제한다.
-
HEADER_NODE 는 필수적인 존재이므로, 해당 HEADER_NODE 를 추가한다.
-
Node 객체를 구현한다.
구현 코드
package com.study;
import java.util.ArrayList;
public class LinkedList<T> {
Node<T> HEADER_NODE = new Node<T>();
ArrayList<Node> node_list = new ArrayList<Node>();
public LinkedList(){
node_list.add(HEADER_NODE); // 처음에 넣고 시작해야 하므
}
private void next(Node node, int dest_head){
node.setNEXT_HEAD(dest_head);
}
private void previous(Node node, int previous_head){
node.setPREVIOUS_HEAD(previous_head);
}
public void add(T value){
Node<T> new_node = new Node<>(value);
node_list.add(new_node);
int index = node_list.indexOf(new_node);
if(index == 1) {
new_node.setPREVIOUS_HEAD(HEADER_NODE.getAdrress());
HEADER_NODE.setNEXT_HEAD(new_node.getAdrress());
}else if(index == node_list.size()-1){
setPreviousNode(new_node, index);
new_node.setNEXT_HEAD(HEADER_NODE.getAdrress());
}else{
setPreviousNode(new_node, index);
setNextNode(new_node, index);
}
}
private void setNextNode(Node<T> new_node, int index) {
Node next_node = node_list.get(index +1);
int next_addr = next_node.getAdrress();
new_node.setNEXT_HEAD(next_addr); // 다음 주소로 확
}
private void setPreviousNode(Node<T> new_node, int index) {
Node previous_node = node_list.get(index -1);
int pre_node_addr = previous_node.getAdrress();
new_node.setPREVIOUS_HEAD(pre_node_addr); // 이전 주소로 확립
}
public Node get(int index){
return node_list.get(index);
}
public void remove(Node node){
//TODO : delete connection && remove value && connection Establish
//You Don't Remove HEADER NODE
if(!node_list.contains(node)){
throw new IllegalArgumentException("없는 node 입니다.");
}else{
int _pre_node_idx = node_list.indexOf(node)-1;
int _nex_node_idx;
Node preNode;
Node nextNode = null;
boolean action = true;
if(node_list.indexOf(node) != node_list.size()-1){
_nex_node_idx = node_list.indexOf(node)+1;
nextNode = node_list.get(_nex_node_idx);
}else{
action = false;
_nex_node_idx = 0;
}
int _del_node_pre_head = node.getPREVIOUS_HEAD();
int _del_node_nex_head = node.getNEXT_HEAD();
preNode = node_list.get(_pre_node_idx);
preNode.setNEXT_HEAD(_del_node_nex_head);
if(action){
nextNode.setPREVIOUS_HEAD(preNode.getAdrress());
}
node_list.remove(node);
}
}
public void IsConnected(){
//TODO : autoGenerated Connected
}
static class Node<T>{
T value;
int PREVIOUS_HEAD;
int NEXT_HEAD;
public Node(){
}
public Node(T value){
this.value = value;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public int getPREVIOUS_HEAD() {
return PREVIOUS_HEAD;
}
public void setPREVIOUS_HEAD(int PREVIOUS_HEAD) {
this.PREVIOUS_HEAD = PREVIOUS_HEAD;
}
public int getNEXT_HEAD() {
return NEXT_HEAD;
}
public void setNEXT_HEAD(int NEXT_HEAD) {
this.NEXT_HEAD = NEXT_HEAD;
}
public int getAdrress(){
return System.identityHashCode(this);
}
}
}
메인 로직에서 실행 과정
-
노드간의 주소 설정이 제대로 되어 있는지 확인한다.
-
연결을 끊어도 제대로 동작하는지 연결이 확립되어 있는지 확인한다.
느낀점
CS 기초 지식에 대해 공부하다보면, 이걸 구현하는 재미도 있을 뿐더러, 왜 구현하게 되었는지 알 수 있다. 예를들면 이번 LinkedList 같은 경우는 initial setup 이 아닌, 동적으로 계속해서 Node 들을 만들어 줘야 하므로, 메모리 공간의 확보는 유용하게 사용할 수 있으나, 만약 Input 이 많은 Process 에서 사용된다면, 동적으로 Node 를 생성하고, 연결을 확립시키는 logic 이 반복되므로, 데이터의 입출력 그리고 삭제 환경이 적다면, 연결리스트로 메모리 공간의 효율성을 늘리는 것이 좋을 것같고, 데이터의 입출력 그리고 삭제가 많다면 연결리스트의 사용을 고려해 보는것이 좋을 것 같다.
P.S ) 참고로 코드는 조금 번잡할수 있습니다. 😭😭😭
Git-HuB : https://github.com/tmdgusya/AlgoAndDA
👻👻
