티스토리 뷰
public class Node<T> {
public T data;
public Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
public class MySingleLinkedList<T> {
public Node<T> head = null;
public int size = 0;
public MySingleLinkedList() {}
public void addFirst(T item) {
Node<T> newNode = new Node<T>(item);
newNode.next = head;
head = newNode;
size++;
}
public void addAfter(Node<T> before, T item) {
Node<T> newNode = new Node<T>(item);
newNode.next = before.next;
before.next = newNode;
size++;
}
// 연결리스트의 index번째 위치에 새로운 데이터를 삽입한다.
public void add(int index, T item) {
if (index < 0 || index > size) {
return; // 추후에 throw
}
if (index == 0) {
addFirst(item);
} else {
Node<T> node = getNode(index - 1);
addAfter(node, item);
}
}
public T removeFirst() {
if (head == null) {
return null;
} else {
T temp = head.data;
head = head.next;
size--;
return temp; // 삭제된 데이터 리턴
}
}
public T removeAfter(Node<T> before) {
if (before.next == null) {
return null;
} else {
T temp = before.next.data;
before.next = before.next.next;
size--;
return temp; // 삭제된 데이터 리턴
}
}
// index 번째 노드를 삭제하고, 그 노드에 저장된 데이터 반환
public T remove(int index) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
return removeFirst();
} else {
Node<T> prev = getNode(index - 1);
return removeAfter(prev);
}
}
// item 을 가진 노드를 찾아 삭제한다. 삭제된 노드에 저장된 값을 리턴
public T remove(T item) {
Node<T> p = head;
Node<T> q = null;
while ( p!= null && !p.data.equals(item)) {
q = p;
p = p.next;
}
if (p == null) { // 삭제할 노드가 존재하지 않는 경우, LinkedList가 empty일 경우
return null;
}
if (q == null) {
return removeFirst(); // 찾고있는 노드가 첫 번째 노드일 경우
} else {
return removeAfter(q); // 일반적인 경우
}
}
// 검색
public int indexOf(T item) {
Node<T> p = head; // 임시값
int index = 0;
while (p != null) {
if (p.data.equals(item)) {
return index;
}
p = p.next;
index++;
}
return -1;
}
// 연결리스트의 index번째 노드의 주소를 반환한다 .
public Node<T> getNode(int index) {
if (index < 0 || index >= size) {
return null;
}
Node<T> p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
// index번째 노드에 저장된 데이터를 반환한다.
public T get (int index) {
if (index < 0 || index >= size) {
return null;
}
Node<T> p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
// return getNode(index).data; 로 표현가능
// 이렇게 사용 할 경우 위에 if문은 필요하다
}
}
※참조
www.youtube.com/watch?v=3BMnWg5k0fU&list=PL52K_8WQO5oWz_LYm3xg23m5q9qJXoE4n&index=39
반응형
'Algorithm' 카테고리의 다른 글
트리 정리 (0) | 2020.09.07 |
---|---|
그리디&구현, DFS&BFS (0) | 2020.09.01 |
EOF (End of File) (0) | 2020.08.29 |
정렬 정리 (0) | 2020.08.27 |
검색 정리 (0) | 2020.07.13 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 패스트캠퍼스 컴퓨터공학 완주반
- js array
- HTTP 완벽가이드
- 드림코딩
- 킹수빈닷컴
- 백준
- 이펙티브자바 아이템60
- http
- 프로그래머스 SQL
- 김영한 http
- 김영한 JPA
- HTTP 완벽 가이드
- 집 구하기
- GCP
- 모던자바스크립트
- js api
- REST API
- JPA 연관관계 매핑
- 백기선 스터디
- Spring Security
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 이펙티브자바 스터디
- js promise
- dreamcoding
- BOJ
- 이펙티브자바 아이템59
- JS 딥다이브
- java
- 이펙티브자바
- 프로그래머스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
글 보관함