728x90
반응형
[자료 구조] 6. 연결 리스트
1. 연결 리스트(Linked List)란?
2. 연결 리스트 구현하기
1. 연결 리스트(Linked List)란?
-연결 리스트는 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조를 말한다.
-자료를 저장하는 노드에는, 본인의 자료와 다음 요소를 가리키는 링크(포인터)가 있다.
-자료가 추가될 때, 노드 만큼의 메모리를 할당 받고, 이전 노드의 링크로 연결한다.
(정해진 크기가 없다.)
-검색할 때에는 배열이 더욱 빠르지만, 데이터를 추가하거나, 삭제 할 때에는 연결 리스트가 더욱 용이하다.
*jdk 클래스: LinkedList
2. 연결 리스트 구현하기
-하나의 요소를 저장하는 기능 설계
*자기 참조(셀프 참조, Self Reference): 객체가 자신과 같은 타입의 다른 객체를 가리키는 경우를 말한다.
연결 리스트, 트리 구조에 많이 활용된다.
package Structure.ch04;
public class Node {
private String data;
// 셀프 참조 = 자기 참조
// 자기 참조는 객체가 자신과 같은 타입의 다른 객체를
// 가리키는 경우를 말합니다.
// 용도 : 연결 리스트, 트리 구조에 많이 활용 됩니다.
public Node next;
public Node() {
data = null;
next = null;
}
public Node(String data) {
this.data = data;
next = null;
}
public Node(String data, Node link) {
this.data = data;
next = link;
}
public String getData() {
return data;
}
}
package Structure.ch04;
import java.util.LinkedList;
public class MyLinkedList {
private Node head; // 요소의 맨 처음을 가리킴
private int count; // 링크드 리스트의 몇 개의 요소가 연결되어 있는 갯수
// MyLinkedList 맨 처음 생성시, 노드는 없는 상태이다.
public MyLinkedList() {
head = null;
count = 0;
}
// 저장된 노드의 갯수를 반환하는 메서드
public int getCount() {
return count;
}
// 새로운 노드(Node Class)를 한 개 추가하는 메서드를 만들자.
public Node addElement(String data) {
Node createNode = new Node(data);
if(head == null) {
// 맨 처음 요소를 저장하는 동작
head = createNode;
} else {
// 항상 요소 찾기는 head에서부터 시작!
Node preNode = head;
while(preNode.next!= null ) {
preNode = preNode.next;
}
// 핵심 코드
preNode.next = createNode;
}
count++;
return createNode; // 추후 수정
} // end of class
public Node removeElement(int index) {
// 방어적 코드 작성
// 0,1
if(index >= count) {
System.out.println("삭제할 위치 오류. 현재 리스트 갯수는 "+count+"개 입니다.");
return null;
}
// 맨 앞 요소를 삭제 요청 시
// 항상 요소를 찾을 때 시작은 head 부터 시작이다.
Node tempNode = head;
if(index == 0) {
// 코드 시작 전 모습
// [야스오][티모. 주소값] --> [티모][null]
head = tempNode.next;
// 코드 수행 후 모습
// [티모][null]
} else {
// 코드 시작 전 모습 : position -> 2이라고 가정 -> n-1 -> 1
// [야스오][티모. 주소값] --> [티모][소라카. 주소값] -->[소라카][null]
Node preNode = null;
for(int i = 0; i < index; i++) {
preNode = tempNode;
tempNode = tempNode.next;
}
preNode.next=tempNode.next;
} // end of if
count--;
System.out.println(index + " 번째 요소를 삭제 했습니다.");
return tempNode; // 추후 수정
}
// 전체 출력 하는 기능 만들기
public void printAll() {
if(count == 0) {
System.out.println("출력할 내용이 없습니다.");
return;
}
Node temp = head;
while(temp != null) {
System.out.print(temp.getData());
temp = temp.next;
if(temp != null) {
System.out.print("-->");
}
}
System.out.println();
}
// 지정한 위치의 노드 하나만 출력 하기
public Node getNodeByIndex(int index) {
if(index >= count) {
System.out.println("검색 위치 오류 - 잘못된 요청");
}
Node tempNode = head;
if(index == 0) {
return head;
}
for(int i=0; i==index; i++) {
tempNode=tempNode.next; // 다음 요소
}
return tempNode;
}
// 전체 삭제 기능 구현
public void removeAll() {
head =null;
count=0;
}
// 테스트 코드
public static void main(String[] args) {
MyLinkedList linkedList = new MyLinkedList();
linkedList.addElement("야스오");
linkedList.addElement("티모");
linkedList.addElement("소라카");
linkedList.printAll();
linkedList.removeElement(1);
linkedList.printAll();
// [야스오][] --> [티모][] --> [소라카][]
System.out.println(linkedList.getCount());
System.out.println(linkedList.getNodeByIndex(1).getData());
linkedList.removeAll();
linkedList.printAll();
}
} // end of class
728x90
반응형
'자료 구조 > 기본 개념' 카테고리의 다른 글
[자료 구조] 8. List 인터페이스 (0) | 2024.05.09 |
---|---|
[자료 구조] 7. 컬렉션 프레임 워크 (0) | 2024.05.09 |
[자료 구조] 6. 큐 구현하기 (0) | 2024.05.07 |
[자료 구조] 5. 비선형 자료 구조 (0) | 2024.05.03 |
[자료 구조] 4. 배열을 활용해 Stack 구현하기 (0) | 2024.05.03 |