❔Object
Linked-List를 자바로 구현 할 것이다.
갑자기 Linked-List?
예전에 자료구조&알고리즘을 배울땐 C언어로 배웠었다.
당시에 배열로 스택을 표현하는 것은 큰 문제 없이 가능은 했으나 큐는 배열로 표현하는 순간 배열 공간의 한계가 있다는 걸 알았었다.
연결리스트로 표현하는 것이 좋기 때문에 Java로 큐를 구현 하기 전에
자바로 연결리스트를 어떻게 구현하는지 알아보려고 한다.
delete 까진 설명 안하고 insertNode의 Logic을 깊게 설명 하면서 마무리 할 예정.
📚CHRACTERISTICS
- head와 tail ( Linked-List )
head : 연결리스트의 첫 노드를 가리킴.Enterance
tail : 연결리스트의 마지막 노드를 가리킴.Exit
insertNode : 노드 삽입(마지막, 중간, 처음)
deleteNode: 노드 삭제(마지막, 중간,처음)
(...)
- data와 link ( listNode )
data : 저장할 데이터 값
link : 다음 노드를 가리킴.
위에 특성들을 보면 Linked-List와 listNode가 존재한다.
Linked-List는 연결리스트에 접근하게끔 해주는 입구와 출구 같은 역할을 해주고
ListNode는 연결리스트를 구성하고 있다.
두개로 분리 된 역할들인데 객체지향적 관점으로 이 각각을 클래스로 만들고 연결리스트를 구현 할 것이다.
⚙️Build
연결리스트 노드 구현
class ListNode{
private int data;
ListNode link;
ListNode(){
this.data = 0;
this.link = null;
}
int getData(){
return this.data;
}
}완성된 ListNode Class
연결리스트의 노드는 연결된 리스트에 하나의 데이터를 뜻한다.
이 노드들은 어떠한 멤버 변수들을 가져야 노드들 여럿을 연결시킬 수 있고 또 연결 시킴으로써 연결리스트를 만들어 낼 수 있을까?
class ListNode{
private int data;
ListNode link;
(...)실질적으로 표현하고자 하는 데이터는 당연 존재 할 것이고,
연결 시키기 위해서는 다른 ListNode 객체를 가리킬 수 있는 link 참조 변수가 필요한 것이다.
근데 왜 data는 private이고 link는 아니냐?
data는 실질적으로 Linked-List Class에서 직접 Control 하는 부분이 아니다.
왜냐면 Linked-List Class는 ListNode간의 link를 이용하여 연결리스트를 관리하는데
그 부분에 있어 data는 필요하지 않다.
(따로 getData 함수를 만들어 data를 추출하는 것이 맞는듯 하다.)
연결리스트 (Manager) 구현
정확히 연결리스트 Manager라는 표현이 맞는 Class가 아닌가 싶다.
이 클래스를 통해 노드를 생성해서 삽입하고 삭제하고 탐색하고 출력하기 때문이다.
우선 숨막힘 주의..
class LinkedList{
private ListNode head;
private ListNode tail;
LinkedList(){
head = null;
tail = null;
}
//마지막에 Node 삽입
void insertNode(int data){
ListNode newNode = new ListNode(data);
//연결리스트가 비었을때
if(this.head == null){
this.head = newNode;
this.tail = newNode;
}
else{
this.tail.link = newNode;
this.tail = newNode;
}
}
//중간에 노드 삽입( k번째에 노드 삽입, k>=1 )
void insertNode(int k, int data){
ListNode newNode = new ListNode(data);
ListNode tempNode = this.head;
ListNode tempNodePre = null;
for(int i=0; i<k-1; i++){
tempNodePre = tempNode;
tempNode = tempNode.link;
}
//노드가 하나 있을때
if(this.head == tempNode){
newNode.link = this.head;
this.head = newNode;
}
else{
tempNodePre.link = newNode;
newNode.link = tempNode;
if(newNode.link == null)
this.tail = newNode;
}
}
//마지막 노드 삭제
void deleteNode(){
if(this.head == null)
System.out.println("List is Empty!!");
else{
ListNode tempNode = this.head;
while(tempNode.link != this.tail)
tempNode = tempNode.link;
tempNode.link = null;
this.tail = tempNode;
}
}
//중간 노드 삭제
void deleteNode(int k){
if(this.head == null)
System.out.println("List is Empty");
else{
if(this.head == this.tail){
this.head = null;
this.tail = null;
}
else{
ListNode tempNode = this.head;
ListNode tempNodePre = null;
for(int i=0; i<k-1; i++){
tempNodePre = tempNode;
tempNode = tempNode.link;
}
if(tempNode == this.head)
this.head = tempNode.link;
else{
tempNodePre.link = tempNode.link;
if(tempNode.link == null)
this.tail = tempNodePre;
}
}
}
}
void printList(){
ListNode tempNode = this.head;
while(tempNode != null){
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.link;
}
System.out.println();
}
}
완성된 Linked-List Class
하나하나 뜯어서 살펴보자.
[Head, Tail]
class LinkedList{
private ListNode head;
private ListNode tail;
LinkedList(){
head = null;
tail = null;
}
(...)Head는 ListNode 클래스의 객체를 가리킨다.
연결리스트들을 노드간의 연결이 돼 있는 걸로만 구현하면 의미가 없다.
그 시작점이 어딘지 기억해놔야 우리가 접근이 가능하기 때문에, Head를 만들어 주는 것이다.
Tail은 부수적인 멤버변수이긴 하나 있으면 좋다.
있으면 굉장히 유용한 이유는 노드 삽입 및 노드 삭제와 관련 돼 있다.
노드 삽입은 통상적으로 맨 마지막에 노드를 붙이는 것을 말한다.
Head를 통해 연결리스트의 첫번째 노드로 접근을 하는데, 여기서 맨 마지막 노드가 무엇인지 찾기 위해서는 O(n)의 시간이 걸리므로 굉장히 비효율적이다.
맨 마지막 노드를 찾는 이유는 맨 마지막 노드.link에 삽입 할 newNode를 연결 시키기 위함이다.
그렇기 때문에 Tail을 생성해서 마지막 노드를 기억해주면 노드 삽입은 O(1)시간에 일어나기 때문에 있으면 유용하다.
[ INSERT NODE (마지막,중간,처음) ]
이제 노드 삽입으로 넘어간다.
노드 삽입에는 세가지 경우를 전부 생각 해 줘야한다.
- 마지막 노드 삽입 + 처음 노드 삽입(예외처리)
void insertNode(int data){
ListNode newNode = new ListNode(data);
//연결리스트가 비었을때
if(this.head == null){
this.head = newNode;
this.tail = newNode;
}
else{
this.tail.link = newNode;
this.tail = newNode;
}
}
(...)맨 끝에 노드를 삽입하는 것은 한가지 고려해줘야한다.
연결리스트가 비었을때이다.
만약 연결리스트가 비어 있지 않을때는 엄청 간단하다.
그냥 tail이 가리키는 노드의 link와 새로운 newNode를 연결 시켜주면 그만이다.
head를 갱신 할 필요가 전혀 없다.
근데, 만약 연결리스트가 비어 있다면?
tail 가지고 마지막 노드를 표현 하는 것만으로 부족하다.
왜냐면 head의 link를 새로운 노드로 갱신 시켜줘야 되기 때문에,
if문을 통해서 해당 부분을 예외처리 해준다.
이와 같이 오류가 날 수 있는 여러 상황들을 생각해서 정확한 예외처리를 해주는게 올바른 연결리스트를 만드는 지름길이 아닌가 싶다.
노드를 중간에 삽입할땐 또 다른 예외처리를 해주어야 한다.
- 중간 노드 삽입
//중간에 노드 삽입( k번째에 노드 삽입, k>=1 )
(...)
void insertNode(int k, int data){
ListNode newNode = new ListNode(data);
ListNode tempNode = this.head;
ListNode tempNodePre = null;
for(int i=0; i<k-1; i++){
tempNodePre = tempNode;
tempNode = tempNode.link;
}
(..)k번째에 노드를 삽입 하는 경우다.
예를 들어 보자.
(K=3 인 경우)3번째에 노드를 삽입 하는 경우는 3번째에 있는 노드 앞에다가 노드를 삽입한다는 뜻이다.
즉, 새로운 노드가 잘 삽입 된 결과의 연결리스트를 봤을때 2번째에 위치 해야 한다는 소리
그리고 중간에 노드를 삽입하려면 삽입하려는 그 위치에 그 앞에 있는 노드와 그 뒤에 있는 노드가 무엇인지 기억할 필요가 있다.
삽입 할 위치 전의 노드.link를 새로운 노드로 가리키게 하고 새로운 노드.link를 삽입 할 위치 전의 노드가 원래 가리키고 있던 노드로 갱신 해줘야 노드를 중간 삽입 하고 나서도 올바른 연결리스트가 된다.
그래서 tempNodePre(삽입 할 위치 전의 노드), tempNode(삽입 할 위치 뒤의 노드)를 만든 것이다.
또,, 아직 남아 있다.
여기서 우린 1번째(맨 앞)에 노드를 삽입 하는 경우를 생각 해 볼 필요가 있다.
//새로운 노드를 맨 앞에 삽입 할때,
if(this.head == tempNode){
newNode.link = this.head;
this.head = newNode;
}
//중간 노드 삽입
else{
tempNodePre.link = newNode;
newNode.link = tempNode;
if(newNode.link == null)
this.tail = newNode;
}
}
(...)맨 앞에 노드를 삽입 한다고 했을때 head를 갱신 시켜줄 필요가 있다는 것을 인지하자.
🤣Conclusion
C언어로 구현 했던 때랑 거의 차이가 없다.
솔직히 사용하는 Logic은 아에 똑같다.
단지 언어마다 어떻게 표현하는지 그 차이가 있는 듯 한데,
해당 연결리스트를 구현하면서 자바로는 이런식으로 구현 하는 것을 깨닫는 정말 유익한 시간이었다.
앞에서 생략은 헀지만 deleteNode 또한 마찬가지다.
insertNode와 같은 원리로 deleteNode도 직접 보면서 코드를 따라 치면 이해 할 수 있다.
연결리스트에서 가장 중요한 점은 삽입하든 삭제하든 앞과 뒤의 노드가 어떤 상태인지 노드가 존재하는지 head가 존재하는지 판단하고 이 부분을 새로운 노드와 잘 갱신 해주는 것이 Point라는 점 있지말자.
외우면 안되고 이해해야한다.
자료구조를 구현하는 코드들은 제각각 다를 수 밖에 없어서, 원리만 이해하고 자기만의 자료구조를 만든 다음에 비교하는 방법이 훨씬 이해에 빠르다는 점 잊지 말자.
