※ 전장에서 공부했든 연결리스트에 대한 기본 구조는 알고 있을 것이다.
노드를 만들 때 C에서는 link 부분을 포인터를 이용했지만 자바에서는 포인터대신 객체를 이용한다.
ex) Node.link.link.link.link 의 방식으로 연결 리스트의 노드를 탐색한다고 생각하자.
※ 자바에서의 포인터개념??
자바에서 포인터 개념을 알기 위해선 메모리 구조에 대해 알아야 한다.
정적 메모리 스텍(Stack) 영역
- 스택 영역은 변수값을 저장하게 되는데 기본타입인 정수형(int/short/char/byte)변수와 실수형(float/double)변수와 논리형(boolean)변수를 실제값으로 저장한다
- 크기가 정해져 있는 타입이다.
- 메모리 할당시 컴파일할때 이미 계산이 이루어진다.
- 메소드 작업이 종료되면 할당되어던 메모리 공간은 반환되어 비워진다.
동적 메모리 힙(Heap) 영역
- 객체와 배열이 생서오디는 공간이고 참조타입(배열,열거,클래스,인터페이스)들을 힙영역에 주소형식으로 저장한다.
- 크기가 정해져 있지 않다.
- 메모리 할당시 프로그램을 실행할때 메모리를 빌려 동적으로 할당한다.
- 참조하는 변수가 없다면 자동으로 힙 영역에서 제거 된다.
즉 여기서 Node의 link 부분을 객체로 만들어서 구현하였는데 객체를 저장할 때 힙 영역에 주소형식으로 저장하므로
자바에서 C처럼 포인터를 사용할 수 없어도 객체를 주소값을 이용해 저장하기 때문에 같은 개념이라 할 수 있는것 같다.
아래는 인터넷에서 찾은 내용이다. 참고해보면 좋을것이다.
Object o1 = new Object();
Object o2 = o1;
이라고 했을 때, o1 객체가 o2 객체로 복사되는 것이 아니라, o1 객체가 참조하고 있는 곳과 똑같은 곳을 참조하도록 할 뿐입니다. o1.hashcode() 와 o2.hashcode() 의 값을 비교해보면 알 수 있겠죠.
포인터 연산만 못하게 되어있을 뿐, 실제로는 포인터라고 볼 수 있겠죠.
즉 o1에는 객체를 가르키는 주소값이 저장되어 있다.
개념 자체는 02-1 연결 자료구조 방식에 충분히 나와있으므로 기본 연결 리스트를 만들어보자.
※ 연결리스트 구현하기
메인
public class class_Ex6_1 {
public static void main(String[] args) {
LinkedList list = new LinkedList();
System.out.println("(1)공백 리스트에 처음과 마지막에 노드 삽입하기");
list.insertFirstNode("화");
list.insertLastNode("수");
list.insertLastNode("토");
list.insertFirstNode("월");
list.insertLastNode("일");
list.printList();
System.out.println("(2)수 노드 뒤에 목,금 노드 삽입하기");
ListNode pre1 = list.searchNode("수");
if(pre1==null){
System.out.println("검색실패>> 찾는 데이터가 없습니다.");
}else{
list.insertMiddelNode(pre1, "목");
ListNode pre2 = list.searchNode("목");
list.insertMiddelNode(pre2, "금");
list.printList();
}
System.out.println("(3)리스트의 노드를 역순으로 바꾸기");
list.reversNode();
list.printList();
System.out.println("(4)리스트의 처음,중간,마지막 노드삭제하기");
ListNode delNode = list.searchNode("수");
list.deleteNode(delNode);
delNode = list.searchNode("일");
list.deleteNode(delNode);
delNode = list.searchNode("월");
list.deleteNode(delNode);
list.printList();
}
}
노드
public class ListNode {
private String data;
public ListNode link;
public ListNode() {
this.data = null;
this.link =null;
}
public ListNode(String data) {
this.data = data;
}
public ListNode(String data, ListNode link) {
this.data = data;
this.link = link;
}
public String getData(){
return data;
}
}
연결리스트
public class LinkedList {
private ListNode head;
public LinkedList() {
this.head = null;
}
public ListNode searchNode(String data){
ListNode temp = head;
while(temp != null){
if(data == temp.getData()){
return temp;
}
else{
temp = temp.link;
}
}
return temp;
}
public void insertMiddelNode(ListNode pre, String data){
if(pre.link ==null){
System.out.println("마지막 노드입니다. insertLastNode함수를 사용하세요.");
return;
}else{
ListNode newNode = new ListNode(data);
newNode.link = pre.link;
pre.link = newNode;
}
}
public void insertLastNode(String data){
ListNode newNode = new ListNode(data);
if(head == null){
head = newNode;
}else{
ListNode temp = new ListNode();
temp=head;
while(temp.link != null){
temp = temp.link;
}
temp.link = newNode;
}
}
public void insertFirstNode(String data){
ListNode newNode = new ListNode(data);
if(head == null){
head = newNode;
}else{
ListNode temp = head;
head = newNode;
newNode.link = temp;
}
}
public void deleteNode(ListNode deleteNode){
if(head==null){
System.out.println("삭제할 리스트가 없습니다.");
return;
}else{
ListNode temp = head;
if(head == deleteNode){
head = deleteNode.link;
}else{
while(deleteNode != temp.link){
temp = temp.link;
}
temp.link = deleteNode.link;
deleteNode.link =null;
}
}
}
public void reversNode(){
if(head ==null){
System.out.println("리스트의 길이가 0입니다.");
return;
}else{
ListNode pre =null;
ListNode current = null;
ListNode next= head;
if(next.link == null){
System.out.println("리스트의 길이가 1입니다. 역으로 정렬하려면 리스트의길이가 2 이상이어야 합니다.");
return;
}
while( next != null){
pre = current;
current = next;
next = next.link;
current.link = pre;
}
head = current;
}
}
public void printList(){
if(head ==null){
System.out.println("리스트의 길이가 0입니다.");
return;
}else{
ListNode temp = head;
int index =0;
while(temp.link != null){
System.out.println("index : "+ index + ", value : " + temp.getData());
temp = temp.link;
index++;
}
System.out.println("index : "+ index + ", value : " + temp.getData());
}
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 02-4 이중 연결 리스트 (0) | 2016.11.25 |
|---|---|
| 02-3 원형 연결 리스트 (0) | 2016.11.25 |
| 02-1 연결 자료구조 방식 (0) | 2016.11.25 |
| 01-3 행열의 순차 자료구조 표현 (0) | 2016.11.25 |
| 01-2 다항식의 순차 자료구조 표현 (0) | 2016.11.25 |
