[자료구조, 알고리즘] 리스트#3 - js로 CircularLinkedList 구현, 자바로 생각해보기

[연결리스트]

- 메모리 상에서는 떨어져있는 데이터 : 각각 연결하여 1열의 개념의 데이터 저장공간을 만듦

- 핵심

(1) node : 현재 데이터와 현재와 연결된 다음 데이터를 가리키는 주소를 함께 저장 - node -> data, next

(2) node 간 어떻게 연결할 것인가, 연결되어져있는 node 탐색방법

- 연결 형태에 따라 단순/원형/양방향 연결리스트 나뉨

[원형 연결리스트]

- 단순 연결리스트와 마찬가지로 단방향 : 역방향까지 지원하는 양방향 연결리스트는 다음 포스팅!

- 처음 추가된 node와 마지막 node가 연결되어 원형을 띔

- 단순 연결리스트는 head -> tail node로 가기위해 tail에서 next node로 순차탐색

=> 위의 그림처럼 head를 둬도 되지만, 원형 연결리스트의 특성을 살리기위해 head보다 tail을 둠

=> 효율적으로 tail과 head를 찾을 수 있음 : 서로 연결되어져있기때문에, tail.next === head

- 원형 연결리스트는 head와 tail 두 node의 주소값을 저장하는 변수를 뒤지않음 : tail의 nextNode로 head가 가리키는 node 참조

=> 얼핏 보기엔 하나의 특성으로 보이겠지만 리스트 ADT를 실제 구현할 때 영향을 미침

- 그렇다고해서 원형 연결리스트가 단순 연결리스트보다 뛰어나다는 것 아님 : 때에 따라 선택해서 사용

- 보통 하드웨어, 시스템 소프트웨어, OS에서 원형 연결리스트를 사용한다고 함 : 메모리 순차 사용

[자바스크립트로 구현하기]

- 객체지향에 더 가까우려면 List ADT - LinkedList - CircularLinkedList 각각 구현해야하지만 지금은 자료구조에 더 집중!

- 코드

var CircularLinkedList = (function(){

var Node = function(data){

this.data = data;

this.next = null;

}

var CircularLinkedList = function(){

this.tail = null;

this.before = null;

this.current = null;

this.length = 0;

};

CircularLinkedList.prototype = {

insert: function(data){

if(!data){

return false;

}

var newNode = new Node(data);

if(this.tail){

var preNode = this.tail;

newNode.next = preNode.next;

preNode.next = newNode;

} else {

newNode.next = newNode;

}

this.tail = newNode;

this.length += 1;

return true;

},

first: function(){

if(this.length < 1){ //노드 길이 0일 때는 첫번째 지정도 안됨

return false;

}

this.before = this.tail; //길이에 상관없이 tail이 before, tail.next가 헤드(current)

this.current = this.tail.next; //1일 때나 2일 때나 결국 같은 노드를 가리킴

return true;

},

next: function(){

if(!this.current || !this.tail){ //노드 길이가 0일 때는 이동안됨

return false;

}

this.before = this.current;

this.current = this.current.next;

return true;

},

remove: function(){

if(!this.current || this.length < 1){ //노드 길이가 0일 때는 삭제안됨

return false;

}

if(this.length === 1){

this.before = null;

this.current = null;

this.tail = null;

this.length = 0;

return true;

}

this.before.next = this.current.next;

this.current = this.before;

this.length -= 1;

return true;

},

count: function(){

return this.length;

}

};

return CircularLinkedList;

})();

var list = new CircularLinkedList();

=> node가 1개라도 순환 : tail과 head가 같음

[자바로 구현 생각해보기: 설계하기]

AS : 객체지향의 사실과 오해 라는 책을 읽고 객체지향에 대한 견해가 정립되어가는 중....
       클래스 중심으로 생각하면서 썼던 이 글을 책을 다읽고 개인 견해가 정리되면 고쳐쓰겠음!
       자바로 구현 생각해보기라고 적어두고 클래스를 너무 강조해서 쓴 것 같아 책을 읽고 있는 와중에 너무 찔려서 추가글을 붙이러옴
       지금까지 읽은 내용에서 얻은 지식(?)을 정리하자면
       (1) 객체 중심의 사고를 하는 것부터가 객체지향 프로그래밍의 시작, 객체는 어플리케이션을 완성하기위해 필요한 역할을 각각 분리
       (2) 각 역할을 맡은 객체는 협력하면서 기능을 완성함 : 메세지를 주고받으면서 객체가 내부적으로 가지고 있는 메서드를 실행시켜 각자가 맡은 역할을 함 -> 결과

       (3) 클래스는 객체지향 프로그래밍을 하기위해 필요한 컴포넌트
       (4) 예시(간단하게) : 커피 주문 서비스에 필요한 객체 - 손님, 캐셔, 바리스타, 커피머신 등
       (5) 책을 보고 나니 객체지향의 특징과 장점이 눈에 보임! 더 넓은 눈을 달고 다시 오겠습니다. 아랫글은 자바 뉴비의 별로 그렇게 썩 좋은 결과가 아닌 흔적..정도로만
     
     

- 초보지만 계속 시도해보면서 실력 느는거지!

- 자바 syntax 공부하고 직접 구현해보기 : 표준 클래스 있지만 하면서 느는거지!

- 자료구조 생각, 객체 파악, 타입 정의, 메시지 - 객체 연결

(1) ListADT abstract class 작성 : 필요한 멤버변수 상속

(2) LinkedList abstract class extends ListADT : ArrayList와는 달리 LinkedList만 가지는 특징과 관련한 멤버변수 상속

(3) simple/circular/doubly LinkedList extends LinkedList