📖본 포스팅은 'think data structures'를 보고 포스팅 되었습니다.
ListNode class
package list;
/**
* 연결 리스트로 요소를 저장하는 List 인터페이스의 일부 구현을 제공
*/
public class ListNode {
public Object data; //어떤 오브젝트에 대한 참조
public ListNode next; // 다음 노드에 대한 참조
public ListNode() {
this.data = null;
this.next = null;
}
public ListNode(Object data) {
this.data = data;
this.next = null;
}
public ListNode(Object data, ListNode next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return "ListNode(" +data.toString() +")";
}
}
노드의 연결 예시
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
Node1.next = node2;
Node2.next = node3;
Node3.nexy = null;
특정 위치에 노드를 추가하는 예시
ListNode node0 = new ListNode(0,node1)
//노드와 링크를 동시에 생성하는 방식으로 위의 생성자가 있기 때문에 가능합니다.
연결 리스트의 객체 다이어그램(구체적으로 그린 버전)
List를 사용해 LinkedList를 구현하여 사용해보기
부제: 특정 구현체 사용 없이 인터페이스를 구현해 사용해보자
LinkedList의 add()와 remove() 함수 설명
가비지 컬렉션
- MyArrayList의 경우엔 배열이 늘어나긴 하지만 줄어들지는 않기 때문에 배열은 가비지 컬렉션을 하지 않고 그 요소도 리스트 자체가 파괴될 때까지 가비지 컬렉션의 대상이 아니다.
- 연결 리스트의 구현의 장점은 요소를 제거하면 리스트 크기가 줄어들고 사용하지 않는 노드는 즉시 가비지 컬렉션이 될 수 있다는 것이다.
- Head 변수를 null로 만들게 되면 첫 번째 Node에 대한 참조를 제거하고 해당 Node에 대한 참조가 없다면 이는 가비지 컬렉션의 대상이 됩니다.
전체 코드
package list;
import java.util.*;
public class MyLinkedList<E> implements List<E> {
private class Node{
public E data;
public Node next;
public Node(E data) {
this.data = data;
this.next = null;
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return "Node(" + data.toString() + ")";
}
}
private int size;
private Node head;
public MyLinkedList() {
this.size = 0;
this.head = null;
}
public static void main(String[] args) {
List<Integer> mll = new MyLinkedList<Integer>();
mll.add(1);
mll.add(2);
mll.add(3);
System.out.println(Arrays.toString(mll.toArray())+" size = "+ mll.size());
mll.remove(new Integer(2));
System.out.println(Arrays.toString(mll.toArray())+" size = "+ mll.size());
}
private boolean equals(Object target, Object element){
if(target == null){
return element == null;
} else{
return target.equals(element);
}
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
@Override
public Iterator<E> iterator() {
E[] array = (E[]) toArray();
return Arrays.asList(array).iterator();
}
@Override
public Object[] toArray() {
Object[] array = new Object[size];
int i = 0;
for (Node node = head; node != null; node = node.next){
array[i] = node.data;
i++;
}
return array;
}
@Override
public <T> T[] toArray(T[] a) {
throw new UnsupportedOperationException();
}
@Override
public boolean add(E e) {
if(this.head == null){
this.head = new Node(e);
} else {
Node node = head;
for (; node.next != null; node = node.next){}
node.next = new Node(e);
}
size++;
return true;
}
@Override
public boolean remove(Object o) {
int index = indexOf(o);
if(index == -1){
return false;
}
remove(index);
return true;
}
@Override
public boolean containsAll(Collection<?> c) {
for(Object obj: c){
if(!contains(obj)){
return false;
}
}
return true;
}
@Override
public boolean addAll(Collection<? extends E> c) {
boolean flag = true;
for (E element: c){
flag &= add(element);
}
return flag;
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
throw new UnsupportedOperationException();
}
@Override
public boolean removeAll(Collection<?> c) {
boolean flag = true;
for(Object obj : c){
flag &= remove(obj);
}
return flag;
}
@Override
public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException();
}
@Override
public void clear() {
/**
* 해당 Node의 head가 null일 경우애
* 우리는 LinkedList가 비어있다고 생각하기에 초기화 해주면 된다.
* **/
head = null;
size = 0;
}
@Override
public E get(int index) {
Node node = getNode(index);
return node.data;
}
private Node getNode(int index) {
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException();
}
Node node = head;
for (int i = 0; i < index; i++){
node = node.next;
}
return node;
}
@Override
public E set(int index, E element) {
Node node = getNode(index);
E old = node.data;
node.data = element;
return old;
}
@Override
public void add(int index, E element) {
/**
* 해당 index에 element를 추가하는 방식
* 앞 뒤 node를 재설정 해주어야 한다.
* **/
if (index == 0){
//맨 앞에 요소를 넣어줄 땐 현재 head를 next로 넣어준다.
head = new Node(element,head);
} else {
/**
* 1. 현재 삽입하려는 index 앞에 있는 노드를 가져온다.
* 2. 현재 노드의 next에 현재 넣으려는 요소를 다음 노드로 설정한다.
* (삽입하려는 위치 앞에 노드에 연결해주는 것이라고 생각하면 된다.)
* 3. 해당 index 앞에 노드의 뒤에 연결된 노드를 현재 삽입하고자하는 노드의 next로 연결해주어야 한다.
* **/
Node node = getNode(index-1);
node.next = new Node(element, head.next);
}
size++;
}
@Override
public E remove(int index) {
E element = get(index);
if (index == 0){
head = head.next;
} else {
//해당 index 앞의 값을 가져와 제거하고자 하는 index의 next에 연결해준다.
Node node = getNode(index-1);
node.next = node.next.next;
}
size--;
return element;
}
@Override
public int indexOf(Object target) {
Node node = head;
for (int i = 0; i <size; i++){
if(equals(target, node.data)){
return i;
}
node = node.next;
}
return -1;
}
@Override
public int lastIndexOf(Object target) {
Node node = head;
int index = -1;
for(int i = 0 ; i < size; i++){
if(equals(target,node.data)){
index = i;
}
}
return index;
}
@Override
public ListIterator<E> listIterator() {
return null;
}
@Override
public ListIterator<E> listIterator(int index) {
return null;
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
if(fromIndex < 0 || toIndex >= size || fromIndex > toIndex){
throw new IndexOutOfBoundsException();
}
int i = 0;
MyArrayList<E> list =new MyArrayList<E>();
for(Node node = head; node != null; node = node.next){
if(i >= fromIndex && i <= toIndex){
list.add(node.data);
}
i++;
}
return list;
}
}
'Back-End > 백엔드 관련 정리' 카테고리의 다른 글
[javascript][open data] - 공공포털 데이터를 사용해보자 (0) | 2022.10.04 |
---|---|
[자바][다시 개념 정리] - 객체 지향 프로그래밍? (0) | 2022.09.24 |
[자바][List] - 인터페이스 기반 프로그래밍 (0) | 2022.09.17 |
[백엔드 과정][자바 기초] - 1. 스레드(Thread) (0) | 2022.09.06 |
[백엔드 과정][자바 기초] - 프로세스 (0) | 2022.09.06 |