Practice1 중복값 삭제하기
class Node {
int data;
Node next;
Node() {
}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList() {
}
LinkedList(Node node) {
this.head = node;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public boolean findData(int data) {
if (this.isEmpty()) {
// System.out.println("List is empty");
}
Node cur = this.head;
while (cur != null) {
if (cur.data == data) {
// System.out.println("Data exist!");
return true;
}
cur = cur.next;
}
// System.out.println("Data not found!");
return false;
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
public class Practice1 {
public static LinkedList removeDup(LinkedList listBefore) {
LinkedList listAfter = new LinkedList();
Node cur = listBefore.head;
while (cur != null) {
if (listAfter.findData(cur.data) == false) {
listAfter.addData(cur.data);
}
cur = cur.next;
}
return listAfter;
}
public static void main(String[] args) {
// Test code
LinkedList linkedList = new LinkedList();
linkedList.addData(1);
linkedList.addData(3);
linkedList.addData(3);
linkedList.addData(1);
linkedList.addData(4);
linkedList.addData(2);
linkedList.addData(4);
linkedList.addData(2);
linkedList.showData(); // 1 3 3 1 4 2 4 2
linkedList = removeDup(linkedList);
linkedList.showData(); // 1 3 4 2
}
}Node 클래스
-연결 리스트의 단일 요소를 나타냄
-data : 노드가 저장하는 정수 데이터
-next : 다음 노드를 가리키는 참조
-생성자 : Node(int data, Node next) 는 주어진 데이터와 다음 노드 참조로 노드를 초기화
LinkedList 클래스
-단일 연결 리스트를 나타냄
-head : 리스트의 첫 번째 노드를 가리키는 참조
-기본 생성자와 노드를 받아 초기화하는 생성자가 있음
-isEmpty() : 리스트가 비어 있는지 확인. 비어있으면 true 반환
-addData(int data) : 리스트의 끝에 데이터를 추가. 리스트가 비어있으면 새로운 노드를 해드로 설정
-removeData(int data) : 주어진 데이터를 가진 노드를 리스트에서 삭제. 리스트가 비어있으면 메세지를 출력
-findData(int data) : 주어진 데이터를 가진 노드가 리스트에 있는지 확인하고, 존재하면 true 를 반환
-showData() : 리스트의 모든 데이터를 출력. 리스트가 비어있으면 메세지를 출력
Practice1 클래스
-removeDup(LinkedList listBefore) : 중복 값을 제거하는 메서드. 입력 리스트를 순회 하면서 새로운 리스트에 중복 없이 노드를 추가
Practice2 Palindrome 확인하기
public class Practice2 {
public static boolean checkPalindrome(LinkedList list) {
Node cur = list.head;
Node left = list.head;
Node right = null;
int cnt = 0;
while (cur != null) {
cnt++;
right = cur;
cur = cur.next;
}
Node prevRIght = right;
for (int i = 0; i < cnt / 2; i++) {
if (left.data != right.data) {
return false;
}
left = left.next;
right = left;
while (right.next != prevRIght) {
right = right.next;
}
}
return true;
}
public static void main(String[] args) {
// Test code
LinkedList linkedList = new LinkedList();
linkedList.addData(1);
linkedList.addData(3);
linkedList.addData(5);
linkedList.addData(3);
linkedList.addData(1);
System.out.println(checkPalindrome(linkedList));
LinkedList linkedList2 = new LinkedList();
linkedList2.addData(3);
linkedList2.addData(5);
linkedList2.addData(5);
linkedList2.addData(3);
System.out.println(checkPalindrome(linkedList2));
LinkedList linkedList3 = new LinkedList();
linkedList3.addData(1);
linkedList3.addData(3);
linkedList3.addData(5);
linkedList3.addData(1);
System.out.println(checkPalindrome(linkedList3));
}
}Node 클래스
-연결 리스트의 단일 요소를 나타냄
-data : 노드가 저장하는 정수 데이터
-next : 다음 노드를 가리키는 참조
-생성자 : Node(int data, Node next) 는 주어진 데이터와 다음 노드 참조로 노드를 초기화
LinkedList 클래스
-단일 연결 리스트를 나타냄
-head : 리스트의 첫 번째 노드를 가리키는 참조
-기본 생성자와 노드를 받아 초기화하는 생성자가 있음
-isEmpty() : 리스트가 비어 있는지 확인. 비어있으면 true 반환
-addData(int data) : 리스트의 끝에 데이터를 추가. 리스트가 비어있으면 새로운 노드를 해드로 설정
-removeData(int data) : 주어진 데이터를 가진 노드를 리스트에서 삭제. 리스트가 비어있으면 메세지를 출력
-findData(int data) : 주어진 데이터를 가진 노드가 리스트에 있는지 확인하고, 존재하면 true 를 반환
-showData() : 리스트의 모든 데이터를 출력. 리스트가 비어있으면 메세지를 출력
Practice2 클래스
-checkPalindrome(LinkedList list) : 주어진 연결 리스트가 회문인지 확인하는 메서드
-리스트의 길이를 계산하고, 리스트의 중간 지점까지 앞과 뒤에서 동시에 비교
-만약 서로 다른 데이터가 있다면 false를 반환하고, 끝까지 확인하면 true를 반환
Practice3 연결 리스트 부분 뒤집기
public class Practice3 {
public static LinkedList reverseList(LinkedList list, int left, int right) {
Node cur1 = null;
Node pre1 = null;
cur1 = list.head;
for (int i = 0; i < left - 1; i++) {
pre1 = cur1;
cur1 = cur1.next;
}
Node cur2 = cur1;
Node pre2 = pre1;
Node after = null;
for (int i = left; i <= right; i++) {
after = cur2.next;
cur2.next = pre2;
pre2 = cur2;
cur2 = after;
}
pre1.next = pre2;
cur1.next = cur2;
return list;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.addData(1);
linkedList.addData(2);
linkedList.addData(3);
linkedList.addData(4);
linkedList.addData(5);
linkedList.showData();
linkedList = reverseList(linkedList, 2, 4);
linkedList.showData();
LinkedList linkedList2 = new LinkedList();
linkedList2.addData(1);
linkedList2.addData(2);
linkedList2.addData(3);
linkedList2.addData(4);
linkedList2.addData(5);
linkedList2.addData(6);
linkedList2.addData(7);
linkedList2.showData();
linkedList2 = reverseList(linkedList2, 3, 5);
linkedList2.showData();
}
}Node 클래스
-연결 리스트의 단일 요소를 나타냄
-data : 노드가 저장하는 정수 데이터
-next : 다음 노드를 가리키는 참조
-생성자 : Node(int data, Node next) 는 주어진 데이터와 다음 노드 참조로 노드를 초기화
LinkedList 클래스
-단일 연결 리스트를 나타냄
-head : 리스트의 첫 번째 노드를 가리키는 참조
-기본 생성자와 노드를 받아 초기화하는 생성자가 있음
-isEmpty() : 리스트가 비어 있는지 확인. 비어있으면 true 반환
-addData(int data) : 리스트의 끝에 데이터를 추가. 리스트가 비어있으면 새로운 노드를 해드로 설정
-removeData(int data) : 주어진 데이터를 가진 노드를 리스트에서 삭제. 리스트가 비어있으면 메세지를 출력
-findData(int data) : 주어진 데이터를 가진 노드가 리스트에 있는지 확인하고, 존재하면 true 를 반환
-showData() : 리스트의 모든 데이터를 출력. 리스트가 비어있으면 메세지를 출력
Practice3 클래스
-reverseList(LinkedList list, int left, int right) : 주어진 연결 리스트에서 left 와 right 사이의 노드드를 반전시키는 메서드
-cur1 과 pre1 을 사용하여 반전 구간의 시작 지점을 찾음
-cur2 와 pre2 를 사용하여 반전 구간의 노드들을 실제로 반전시킴
-반전 후 리스트를 다시 연결
Practice4 문자열 배열을 첫글자 기준으로 연결 리스트에 저장하기
import java.util.HashSet;
class Node {
String data;
Node next;
Node() {}
Node(String data, Node next) {
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
char alphabet;
LinkedList() {}
LinkedList(Node node, char alphabet) {
this.head = node;
this.alphabet = alphabet;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(String data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.data.equals(data)) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public boolean findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return false;
}
Node cur = this.head;
while (cur != null) {
if (cur.data.equals(data)) {
System.out.println("Data exist!");
return true;
}
cur = cur.next;
}
System.out.println("Data not found!");
return false;
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
public class Practice4 {
public static void dataCollect(String[] data) {
HashSet<Character> set = new HashSet<>();
for (String item : data) {
set.add(item.toCharArray()[0]);
}
System.out.println(set);
Character[] arr = set.toArray(new Character[0]);
LinkedList[] linkedList = new LinkedList[set.size()];
for (int i = 0; i < linkedList.length; i++) {
linkedList[i] = new LinkedList(null, arr[i]);
}
for (String item : data) {
for (LinkedList list : linkedList) {
if (list.alphabet == item.toCharArray()[0]) {
list.addData(item);
}
}
}
for (LinkedList list : linkedList) {
System.out.print(list.alphabet + " : ");
list.showData();
}
}
public static void main(String[] args) {
// Test code
String[] input = {"apple", "watermelon", "banana", "apricot", "kiwi", "blueberry", "cherry", "orange"};
dataCollect(input);
System.out.println();
String[] input2 = {"ant", "kangaroo", "dog", "cat", "alligator", "duck", "crab", "kitten", "anaconda", "chicken"};
dataCollect(input2);
}
}Node 클래스
-연결 리스트의 단일 요소를 나타냄
-data : 노드가 저장하는 문자열 데이터
-next : 다음 노드를 가리키는 참조
-생성자 : 기본 생성자와 데이터를 받아 초기화하는 생성자가 있음
LinkedList 클래스
-단일 연결 리스트를 나타냄
-head : 리스트의 첫 번째 노드를 가리키는 참조
-alphabet : 리스트가 저장할 문자열의 첫 글자
-기본 생성자와 노드 및 첫 글자를 받아 초기화하는 생성자가 있음
-isEmpty() : 리스트가 비어 있는지 확인. 비어있으면 true 반환
-addData(String data) : 리스트의 끝에 데이터를 추가. 리스트가 비어있으면 새로운 노드를 해드로 설정
-removeData(int data) : 주어진 데이터를 가진 노드를 리스트에서 삭제. 리스트가 비어있으면 메세지를 출력
-findData(int data) : 주어진 데이터를 가진 노드가 리스트에 있는지 확인하고, 존재하면 true 를 반환
-showData() : 리스트의 모든 데이터를 출력. 리스트가 비어있으면 메세지를 출력
Practice4 클래스
-dataCollect(String[] data) : 주어진 문자열 배열을 첫 글자 기준으로 분류하여 연결 리스트에 저장하는 메서드
-주어진 데이터에서 첫 글자를 추출하여 HashSet에 저장
-첫 글자 기준으로 각기 다른 연결 리스트를 생성
-주어진 데이터를 순회하면서 각 리스트에 데이터를 추가
-각 리스트의 데이터를 출력
