[DS] Array List, Linked List

ArrayList

가장 기본적인 자료구조이며, 논리적 저장 순서와 물리적 저장 순서가 동일한 자료구조

따라서 index로 해당 element에 빠르게 접근이 가능

장점

• 찾고자하는 대상의 index를 알고있으면 O(1)의 매우 빠른 속도로 접근이 가능

단점

• List의 Capacity를 늘릴경우 더 큰 Capacity의 새로운 List에 기존 element들을 모두 복사해야 함

• java에서는 가변길이의 ArrayList가 이미 구현이 되어있지만, ArrayList를 직접 구현을 할 경우 가변 길이는 상황에 맞는 적절한 방법을 사용하여야함
• ex) Default capacity와 number of entries가 같아 질 경우 Default capacity의 2배의 길이로 capacity를 늘림

• 삭제 또는 삽입의 과정에서 삭제 또는 삽입의 대상이 되는 index보다 뒤에 있는 index의 element들을 앞으로 또는 뒤로 한 칸씩 shift하는 과정이 필요함 (비효율)

• best-case : 맨 마지막 index에 삽입하거나 삭제하는 case : O(1)
• worst-case : 맨 처음 index에 삽입하거나 삭제하는 case :O(n)
• 따라서 ArrayList의 삭제 혹은 삽입의 time-complexity는 O(n)으로 오래걸림

 

 

 

LinkedList

각각의 Node들이 Link를 통해 자신 다음에 어떤 Node인지 기억하고있는 방식의 자료구조

장점

• 데이터 입력시 주소가 순차적이지 않아 element를 메모리의 어느곳에나 둘 수 있음 (크기가 동적)
• 삽입, 삭제 시 link가 가리키는 주소만 바꿔주면 되기 때문에 element 삽입, 삭제가 용이

단점

• 원하는 요소를 찾기위해서는 link를 하나하나 타면서 모든 Node를 확인해야하기 때문에 접근속도가 느림 : O(n)
• 결국 삽입, 삭제를 할 때에도 원하는 위치에 가기 위해서는 Node를 하나하나 확인해야하기 때문에 결국 복잡도는 O(n)

 

이렇게 보면 LinkedList는 장점이 별로 없는 것 같지만 다른 자료구조의 근간이 되는 개념이기 때문에 매우 중요함

 

LinkedList의 종류

1.  Singly Linked List (단순 연결 리스트)

     단방향 링크

     이전 노드에 접근하기 위해서는 첫 번째 노드부터 다시 순회해야함

2. Circular Linked List (원형 연결 리스트)

     단방향 링크

     마지막 노드와 첫 번째 노드가 연결된 원형 구조

     이전 노드에 접근하기 위해서 계속 한방향으로 순회하면 됨

3. Doubly Linked List (이중 연결 리스트)

     양방향 링크

     각 노드가 앞 뒤로 연결됨

     이전 노드에 직접 접근 가능

 

ArrayList를 사용한 Bag 구현 예시

public class ArrayBag <T> implements BagInterface <T> {
	
	private  T [] bag;
	private static final int DEFAULT_CAPACITY = 25;
	private int numberOfEntries;
	
	public ArrayBag () {
		this (DEFAULT_CAPACITY);
	} // default constructor
	
	public ArrayBag (int capacity) {
		numberOfEntries = 0;
		T [] tempBag = (T []) new Object [capacity];
		bag = tempBag;
		
	} // constructor with given initial capacity
	
	
	public boolean add(T newEntry) {
		boolean result = true;
		if (isFull()) {
			result = false;
		}
		else {
			bag[numberOfEntries] = newEntry;
			numberOfEntries++;
		}
		return result;
	}
	
	public boolean isFull() {
		return numberOfEntries == bag.length;
	}
	
	public T[] toArray() {
		T[] result = (T[])new Object[numberOfEntries];
		for (int index = 0; index < numberOfEntries; index++) {
			result[index] = bag[index];
		} 
		return result;	
	} //bag자체의 레퍼런스를 그대로 return 하면 다른사람이 주소에 직접 접근을 하는 문제가 생길 수 있다. 
	  //따라서 copy를 만들어 return 하는것이 좋다.
	
	public boolean isEmpty() {
		return numberOfEntries == 0;
	}
	
	public int getCurrentSize() {
		return numberOfEntries;
	}
	
	public int getFrequencyOf(T anEntry) {
		int counter = 0;
		
		for (int index = 0; index < numberOfEntries; index++) {
			if (anEntry.equals(bag[index])){
				counter++;
			}
		}
		return counter;
	}
	
	public boolean contains(T anEntry) {
		boolean found = false;
		
		for (int index = 0; !found && (index < numberOfEntries); index++) {
			if (anEntry.equals(bag[index])) {
				found = true;
			}
		}
		return found;
	}
	
	public void clear() {
		numberOfEntries = 0;
	} //numberOfEntires가 0이 되어도 array자체는 메모리에 남아있다. 하지만 나중에 GC가 collect하기 때문에 상관없음 

	public T remove() {
		T result = null;
		if (numberOfEntries >0) {
			result = bag[numberOfEntries -1];
			bag[numberOfEntries -1] = null;
			numberOfEntries--; //특정 entry를 지우는 것이 아닌 마지막 index에 위치한 entry 삭제 
		}
		return result;
	}
	
	public boolean remove(T anEntry) {
		boolean result = false;
		
		for (int index = 0; index<numberOfEntries; index++) {
			if (anEntry.equals(bag[index])) {
				bag[index] = null;
				result = true;
			}
		}
		return result;
	} //remove된 entry보다 뒤에 있는 entry 들을 한 칸씩 shift해주고 numberOfEntrie--하는 구현이 추가적으로 필요함 
}

LinkedList를 사용한 Bag 구현 예시

public class LinkedBag <T> {
	
	int numberOfEntries = 0;
	Node <T> firstNode = new Node <T> (null);
	
	public boolean add(T newEntry) {
		Node <T> newNode = new Node <T> (newEntry); 
		newNode.next = firstNode; //newNode가 전에 있던 firstNode를 가리키게 함 
		
		firstNode = newNode; //newNode가 새로운 firstNode가 됨 
		numberOfEntries++;
		
		return true;
	}
	
	public T[] toArray() {
		
		T[] result = (T[])new Object[numberOfEntries];
		
		int index = 0;
		Node <T> currentNode = firstNode;
		
		while ((index < numberOfEntries)&&(currentNode != null)) {
			result[index] = currentNode.data;
			index++;
			currentNode = currentNode.next;
		}
		return result;
	}
	
	public int getFrequencyOf(T anEntry) {
		
		int frequency = 0;
		int counter = 0;
		Node <T> currentNode = firstNode;
		
		while ((counter < numberOfEntries)&&(currentNode != null)) {
			if (anEntry.equals(currentNode.data)) {
				frequency++;
			}
			counter++;
			currentNode = currentNode.next;
		}
		
		return frequency;
	}
	
	public boolean contains (T anEntry) {
		boolean found = false;
		Node <T> currentNode = firstNode;
		
		while (!found && (currentNode != null)) {
			if (anEntry.equals(currentNode.data)) {
				found = true;
			} else {
				currentNode = currentNode.next;
			}
		}
		
		return found;
	}
	
	public T remove () {
		T result = null;
		if (firstNode != null) {
			result = firstNode.data;
			firstNode = firstNode.next; // firstNode의 다음 Node를 firstNode로 만들면서 기존 firstNode는 GC가 collect해가게 함 
			numberOfEntries--;
		}
		
		return result;
	}
	
	private Node <T> getReferenceTo(T anEntry){
		boolean found = false;
		Node <T> currentNode = firstNode;
		
		while(!found && (currentNode != null)) {
			if (anEntry.equals(currentNode.data)) {
				found = true;
			} else {
				currentNode = currentNode.next;
			}
		}
		return currentNode;
	}
	
	public boolean isEmpty() {
		
		return numberOfEntries == 0;
	}
	
	public void clear() {
		while (!isEmpty()) {
			remove();
		}
	}
}

class Node <T> {
	public T data; //entry
	public Node next; // link to next node
	
	public Node (T dataPortion) {
		this (dataPortion, null);
	}
	public Node (T dataPortion, Node nextNode) {
		data = dataPortion;
		next = nextNode;
	}
}

reference

Carrano-Data Structures and Abstractions with Java 3rd Edition

https://coding-factory.tistory.com/551