Java 데이터 구조(1) ArrayList 와 LinkedList (Collections)
1. 모든 데이터 구조 (Data Structure) 기본인 Linear Data Structure 의 대표인 ArrayList 랑 LinkedList 을 알아보자.
ArrayList
는 배열을 활용 해서 만든 구조.
public class ArrayList<E>{
private E[] elements;
.......장점(Pros)
1. 빠른 엑세스
데이터 를 불러올때 인덱스(배렬의 숫자 e.g [3] ...) 를 사용하기때문에 매우 빠른 속도로 가져올수 있음 O(1).
2.적은 RAM 사용량
배열 오버헤드만 저장하면 되므로 LinkedList보다 메모리가 효율적입니다.
단점(cons)
1.매우 비효율 적인 중간 삽입/삭제.
결국엔 배열을 사용 하기 때문에 배열 중간에 새로운 데이터를 넣거나 제거하면 뒤에 있는 데이터들을 전부다 한칸식 움직여야함.
e.g
1000 개의 데이타가 있는데 ( E [1000] element)
element[50] 안에 새로운 데이타를 너는 다면 950 개의 데이다 옴기기 작업을 해야 한다는거.
element[50] 을 제거하면 를 너는 다면 950 개의 데이다 앞당기는 작업을 해야 한다는거.
2.동적 크기 조절 오버헤드
ArrayList는 테이타 수가 용량을 초과하면 기본 배열을 동적으로 조절해야 합니다 (expandcapacity()). 이 크기 조절 작업은 시간이 걸릴 수 있음.
4. ArrayList 함수들
기본구조
public class ArrayList<E>{
private E[] elements; //데이타
protected int size; //사이즈
private int capacity=10; // 배열 크기
public ArrayList() {
size = 0;
elements = (E[])(new Object[capacity]);
}
..........기본 함수들
add(E o) : boolean
정보를 넣을때 사용한다, 만약에 배열이 가득찬 경우 expandcapacity() 로 배열 크길를 2배로 만든다 (한칸식 사이즈를 늘리면 되지않냐고 물어보는데, 그러면 미는 작업을 계속 하게됨/비효율).
public boolean add(E o)
{
if(size >= elements.length){
expandcapacity();
}
elements[size] = o;
size++;
return true;
}expandcapacity() : void
만약에 배열이 가득찬 경우 expandcapacity() 로 배열 크길를 2배로 만든다 (한칸식 사이즈를 늘리면 되지않냐고 물어보는데, 그러면 미는 작업을 계속 하게됨/비효율).
1. 두배로 큰 새 배열을 만든 다음 기존에 있는 정보를 넣는다
2. 새 배령을 기존에 쓰던 메인 배열로 한다.
ublic void expandcapacity(){
E[] largerArray = (E[])(new Object[elements.length*2]);
// copy the elements array to the largerArray
for (int i=0; i<size; i++)
largerArray[i] = elements[i];
elements = largerArray;
}
remove() : boolean
해당 데이타/변수 를 제거
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}contains() : boolean
리스가 해당 object/변수 를 포함하고 있는지.
public boolean contains(E o) {
boolean found = false;
for(int i = 0;i < size; i++){
if(elements[i] == null){
return false;
}
if(elements[i].equals(o)){
found = true;
}
}
return found;
}size() : int
리스트 크기를 가져온다
public int size() {
return size;
}
isEmpty() : boolean
리스트가 이어있는지 확인, true or false 로 출력.
public boolean isEmpty() {
return (size==0);
}
clear() : void
리스트 안에 있는것들을 초기화 시킨다
public void clear() {
elements = null;
size = 0;
}
LinkedList
는 node() 라는 오브젝트를 여러게 만들어서 연결 시키는 방법.
장점(Pros)
1. 빠른 중간 삽입/삭제.
Node 하는 object 를 연결하는 방식을 사용 하기 때문에 배열 중간에 새로운 데이터를 넣을때 데이터 이동없이 node 연결 고리만 변경 하면 됨.
2. 크기 조절할필요가 없음.
배열 은 크기 조절 해야 하지만 Linked list 는 클라스/오브젝트(Node) 의 연결(연속) 이 라 크기 조절 할필요가 없음.
단점(cons)
1. 느린 엑세스
인덱스로 요소에 액세스하려면 리스트를 처음부터 또는 끝부터 순회해야 하므로 랜덤 액세스에 대한 시간 복잡도는 O(n).
2.높은 메모리 오버해드
LinkedList는 각 요소가 개별 클라스/오브젝트(Node) 에 저장되므로 ArrayList보다 RAM/메모리 소비를 더 많이함.
데이터를 젇장하는 Node 의 기본 구조 (상황에 따라 prev/next 노드 추가나 , tree 같은경우는 child node 여러개 가 일수 있음).
protected class Node<E>
{
public E element;
public Node<E> next;
public Node(E element)
{ this.element = element;
next = null;
}
}Linked List 의 기본 구조
public class LinkedList<E> //extends AbstractSet<E>
{
protected int numElements;
protected Node<E> firstNode;
// default constructor that creates a new set
// that is initially empty
public LinkedList() {
super();
numElements = 0;
firstNode = null;
}
// constructor for creating a new set which
// initially holds the elements in the collection c
public LinkedList(Collection<? extends E> c) {
this();
for (E element : c) {
add(element);
}
}
.......
add() : boolean
데이터 넣기
public boolean add(E o){
Node<E> newNode = new Node<E>(o);
// add the new node to the front of the list
newNode.next = firstNode;
firstNode = newNode;
numElements++;
return true;
}contains() : boolean
받은 정보랑 같은게 있는지 확인.
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}remove() : boolean
1. 리스트 가 비어있는지 확인 (비어있으면 return false 하고 끝)
2. node 를 하나하나 정검 하기 시작.
3. remove 하고 싶은 node(data) 를 찾으면 앞에 있던 node 의 next node 를 뒤에 있는 remove 하고 싶은 node 의 뒤에 있는 node 로 연결함.
public boolean remove(Object o)
{ // search for the node of the element o in the list
boolean found = false;
if (firstNode!=null)
{ // check if the element is first in list
if ((firstNode.element==null && o==null) ||
(firstNode.element!=null && firstNode.element.equals(o)))
{ found = true;
firstNode = firstNode.next;
numElements--;
}
else
{ // check the other nodes in the list
Node<E> previous = firstNode;
Node<E> current = firstNode.next;
while (current!=null && !found)
{ if ((current.element==null && o==null) ||
(current.element!=null && current.element.equals(o)))
{ found = true;
previous.next = current.next;
numElements--;
}
else
{ previous = current;
current = current.next;
}
}
}
}
return found;
}clear() : void
LinkedList 를 초기화 시킴.
public void clear()
{ firstNode = null;
numElements = 0;
}size() : int
LinkedList 의 크기 를 가져올수 있음
public int size()
{ return numElements;
}
Iterator : Iterator
연결 되어 있는 정보들을 꺼내서 보기 위한 함수
Iterator 에서 hasNext 랑
public class LinkedIterator<E> implements Iterator<E>
{
private Node<E> nextNode;
public LinkedIterator(Node<E> firstNode)
{ nextNode = firstNode;
}
public boolean hasNext()
{ return (nextNode!=null);
}
public E next() throws NoSuchElementException
{ if (!hasNext())
throw new NoSuchElementException();
E element = nextNode.element;
nextNode = nextNode.next;
return element;
}
// remove method not supported by this iterator
public void remove() throws UnsupportedOperationException
{ throw new UnsupportedOperationException();
}
}