목차
LinkedList 구현해보기
💡 학습 목표
1. LinkedList의 특징을 알아 보자
2. LinkedList 구현해 보기
1. LinkedList 의 특징을 알아 보자
- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
- 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
- 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
- jdk 클래스 : LinkedList
2. LinkedList 구현해 보기
하나의 요소를 저장하는 기능 설계
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;
public class MyLinkedList {
private Node head; // 요소의 맨 처음을 가리킴
private int count; // 링크드 리스트에 몇개의 요소가 연결되어 있는지에 대한 개수
// MyLinkedList 맨 처음 생성시 노드는 없는 상태
public MyLinkedList() {
head = null;
count = 0;
}
// 1. 저장된 Node의 개수를 반환하는 메서드
public int getCount() {
return count;
}
// 2. 새로운 노드(Node)를 1개 추가 하는 메서드를 만들자.
public Node addElement(String data) {
Node createNode = new Node(data);
if(head == null) {
// 맨 처음 요소를 저장하는 동작
head = createNode;
} else {
// linkedList에서 요소 찾기는 head부터 시작
Node preNode = head;
while(preNode.next != null) {
preNode = preNode.next;
}
// 핵심 코드
preNode.next = createNode;
}
count++;
return createNode; // 추후 수정
}
// 테스트 코드
public static void main(String[] args) {
MyLinkedList linkedList = new MyLinkedList();
linkedList.addElement("야스오");
linkedList.addElement("티모");
linkedList.addElement("소라카");
System.out.println(linkedList.getCount());
// [야스오][] ---> [티모][] ---> [소라카][]
} // end of main
}// end of class
특정 위치에 요소 삭제 하기
삭제 기능, 전체 출력 기능 추가
package structure.ch04;
public class MyLinkedList {
private Node head; // 요소의 맨 처음을 가리킴
private int count; // 링크드리스트에 몇개의 요소가 연결 되어 있는 개수
// MyLinkedList 맨 처음 생성시 노드는 없는 상태
public MyLinkedList() {
head = null;
count = 0;
}
// 저장된 Node 갯수를 반환하는 메서드
public int getCount() {
return count;
}
// 새로운 노드(Node)를 1개 추가 하는 메서드를 만들자.
public Node addElement(String data) {
Node createNode = new Node(data);
if(head == null) {
// 맨 처음 요소를 저장하는 동작
head = createNode;
} else {
// 항상 요소 찾기는 head 부터 시작
Node preNode = head; // [야스오][](next)
// [야스오][] ---> [티모][] --> [소라카][]
while(preNode.next != null) {
preNode = preNode.next;
}
// 핵심 코드
//[티모][next] --> [next] = [소라카][]
preNode.next = createNode;
}
count++;
return createNode; // 추후 수정
}
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 {
// 코드 시작전 모습 : postion -> 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(positon + " 번째 요소를 삭제 했습니다.");
return tempNode; // todo - 추후 수정
}
// 전체 출력 하는 기능 만들기
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 static void main(String[] args) {
MyLinkedList linkedList = new MyLinkedList();
linkedList.addElement("야스오");
linkedList.addElement("티모");
linkedList.addElement("소라카");
linkedList.addElement("애쉬");
linkedList.addElement("가렌");
linkedList.printAll();
linkedList.removeElement(4);
linkedList.printAll();
// [야스오][] ---> [티모][] ----> [소라카][]
//System.out.println(linkedList.getCount());
} // end of main
} // end of class야스오-->티모-->소라카-->애쉬-->가렌
야스오-->티모-->소라카-->애쉬
하나의 요소 출력, 전체 삭제 기능 추가
package structure.ch04;
import java.util.LinkedList;
public class MyLinkedList {
private Node head; // 요소의 맨 처음을 가리킴
private int count; // 링크드 리스트에 몇개의 요소가 연결되어 있는지에 대한 개수
// MyLinkedList 맨 처음 생성시 노드는 없는 상태
public MyLinkedList() {
head = null;
count = 0;
}
// 저장된 Node의 개수를 반환하는 메서드
public int getCount() {
return count;
}
// 새로운 노드(Node)를 1개 추가 하는 메서드를 만들자.
public Node addElement(String data) {
Node createNode = new Node(data);
if(head == null) {
// 맨 처음 요소를 저장하는 동작
head = createNode;
} else {
// linkedList에서 요소 찾기는 head부터 시작
Node preNode = head;
while(preNode.next != null) {
preNode = preNode.next;
}
// 핵심 코드
preNode.next = createNode;
}
count++;
return createNode; // 추후 수정
}
public Node removeElement(int index) {
// 방어적 코드
if (index >= count) {
System.out.println("삭제할 위치 오류. 현재 리스트 개수는 " + count + " 입니다.");
return null;
}
// 맨 앞 요소를 삭제 요청 시
// 항상 요소를 찾을 때 시작 head 부터 시작
Node tempNode = head;
if (index == 0) {
// 코드 시작전 모습
// head --> [야스오][티모집주소] --> [티모][소라카집주소]
head = tempNode.next;
// 코드 수행 후 모습
// head --> [티모][소라집주소]
} else {
// 코드 시작전 모습 : position -> 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(position + " 번째 요소를 삭제 했습니다.");
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.addElement("애쉬");
linkedList.addElement("가렌");
// System.out.println(linkedList.getCount());
linkedList.removeElement(4);
linkedList.printAll();
System.out.println(linkedList.getNodeByIndex(1).getData());
} // end of main
}// end of class
'Java > 자료구조' 카테고리의 다른 글
| List 인터페이스 - 7 (0) | 2024.05.09 |
|---|---|
| 컬렉션 프레임 워크 - 6 (0) | 2024.05.09 |
| 큐(Queue) 구현하기 - 4 (0) | 2024.05.07 |
| 배열을 활용한 Stack 구현해보기 - 3 (0) | 2024.05.03 |
| 자료구조 개론 - 1 (0) | 2024.05.02 |