'줄 세워져 있는 데이터' 또는 '쭉 늘어선 데이터'를 의미한다.
i번째 자리에 원소 x를 삽입한다.
i번째 원소를 삭제한다.
원소 x를 삭제한다.
i번째 원소를 알려준다.
원소 x가 몇 번째 원소인지 알려준다.
리스트의 사이즈(원소의 총 수)를 알려준다.
자바는 언어 자체에서 리스트를 기본 자료구조로 제공하지 않고 java.util 패키지에서 제공한다.
배열을 이용한 리스트 구현은 가장 단순한 구현 방법으로, 메모리의 연속된 공간에서 데이터를 관리한다.
이 방법은 이름과 크기만 정하면 되므로 편리하지만 리스트에 원소가 얼마나 들어올지 예상하기 힘들어 배열을 사용하는 경우 충분한 공간을 확보해야 하는데, 이 작업은 공간 낭비가 심하다.
하지만 배열 방식은 단순하고 효율성이 높아 리스트를 구현하기 좋다.
연결 리스트는 배열의 공간 낭비를 피할 수 있는 자료구조이다.
원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따른다.
각 필드와 작업의 의미
item[] <- 원소들이 저장되는 배열
numItems[] <- 원소자리의 인덱스
add(i,x) <- 리스트의 i번째 원소로 x를 삽입한다.
append(x) <- 리스트 맨 뒤에 원소 x를 추가한다.
remove(i) <- 리스트의 i번째 원소를 삭제한다.
removeItem(x) <- 리스트의 처음으로 나타나는 x를 삭제한다.
get(i) <- 리스트 i번째 원소를 알려준다.
set(i,x) <- 리스트 원소 i를 x로 대체한다.
indexOf(x) <- 원소 x가 리스트의 몇 번째 원소이지 알려준다.
len() <- 리스트의 총 원소 수를 알려준다.
isEmpty() <- 리스트가 빈 리스트인지 알려준다.
clear() <- 리스트를 깨끗이 청소한다.
package list;
public class IntegerArrayList implements InteferListInterface {
private Integer[] item;
private int numItems;
/*
stack의 범위 지정,
static이 없다면 동적으로 바인딩
-> 새 객체가 생성될때 상수(final)가 생성
static이 있다면 정적으로 바인딩
-> 컴파일 시점에서 상수(final)가 생성
*/
private static final int DEFAULT_CAPACITY = 64;
public IntegerArrayList() { //생성자 1
item = new Integer[DEFAULT_CAPACITY];
numItems = 0;
}
public IntegerArrayList(int n) { //생성자 2: n만큼의 stack의 길이 생성
item = new Integer[n];
numItems = 0; //리스트의 총 원소 수
}
// 배열 리스트의 k번째 자리에 원소 x를 삽입하기
public void add(int index, Integer x) {
if(numItems >= item.length || index < 0 || index > numItems) {
/*
예외 처리 -> ArrayIndexOutOfBoundsException
k번째 자리가 0미만이거나
스택의 크기보다 총 원소수가 큰 경우
k가 총 원소수 보다 큰 경우
*/
} else {
for(int i = numItems-1; i>= index; i--)
item[i+1] = item[i] // 우 시프트
item[index] = ;
numItems++;
}
}
//배열 리스트의 맨 뒤에 원소 추가하기
public void append(Integer x) {
if(numItems >= item.length) { /*예외 처리*/ }
else { item[numItems++] = x; }
}
// 배열 리스트의 k번째 원소 삭제하기
public Integer remove(int index) {
if(isEmpty() || index < 0 || index > numItems -1)
return null;
else {
Integer tmp = item[index];
for (int i = index; i<= numItems -2; i++)
item[i] = item[i+1];
numItems--;
return tmp;
}
}
//배열 리스트에서 원소 x 삭제하기
public boolean removeItem(E x) {
int k = 0;
while (k < numItems && ((Comparable)item[k]).compareTo(x) != 0) {
k++;
}
if (k == numItems) {
return false;
} else {
for (int i = k; i < numItems - 1; i++)
item[i] = item[i + 1];
numItems--;
return true;
}
}
// 배열 리스트의 i번째 원소 알려주기
public Integer get(int index) {
if (index >= 0 && index <= numItems - 1) {
return item[index];
} else {
return null;
}
}
// 배열 리스트의 i번째 원소를 x로 대체하기
public void set(int index, E x) {
if (index >= 0 && index <= numItems - 1) {
item[index] = x;
} else { /*예외처리*/ }
}
private final int NOT_FOUND = -12345;
public int indexOf(E x) {
for (int i = 0; i < numItems; i++) {
if (((Comparable) item[i]).compareTo(x) == 0) {
return i;
}
}
return NOT_FOUND;
}
// 배열 리스트의 총 원소수 알려주기
public int len() {
return numItems;
}
// 배열 리스트가 비었는지 알려주기
public boolean isEmpty() {
return numItems == 0;
}
// 배열 리스트 깨끗이 청소하기
public boolean clear() {
item = new Integer[item.length];
numItems = 0;
}
}
public class ArrayList<E> implements ListInterface<E> {
private E [] item;
private int numItems;
private static final int DEFAULT_CAPACITY = 64;
public ArrayList() { // 생성자 1
item = (E[]) new Object[DEFAULT_CAPACITY];
numItems = 0;
}
public ArrayList(int n) { // 생성자 2
item = (E[]) new Object[n];
numItems = 0;
}
// 배열 리스트의 k번째 자리에 원소 x 삽입하기
public void add(int index, E x) {
if (numItems >= item.length || index < 0 || index > numItems) {
/* 에러 처리 */
} else {
for (int i = numItems - 1; i >= index; i--)
item[i + 1] = item[i];
item[index] = x;
numItems++;
}
}
// 배열 리스트의 맨 뒤에 원소 추가하기
public void append(E x) {
if (numItems >= item.length) {
/* 에러 처리 */
} else {
item[numItems++] = x;
}
}
// 배열 리스트의 k번째 원소 삭제하기
public E remove(int index) {
if (index < 0 || index > numItems - 1 || isEmpty()) {
return null;
} else {
E tmp = item[index];
for (int i = index; i < numItems - 1; i++)
item[i] = item[i + 1];
numItems--;
return tmp;
}
}
// 배열 리스트에서 원소 x 삭제하기
public boolean removeItem(E x) {
int k = 0;
while (k < numItems && ((Comparable)item[k]).compareTo(x) != 0) {
k++;
}
if (k == numItems) return false;
else {
for (int i = k; i < numItems - 1; i++)
item[i] = item[i + 1]; //좌 시프트
numItems--;
return true;
}
}
// 리스트의 i번째 원소 알려주기
public E get(int index) { // 첫 원소를 0번째 원소로 표기
if (index >= 0 && index <= numItems-1) return item[index];
else return null;
}
// 배열 리스트의 i번째 원소를 x로 대체하기
public void set(int index, E x) {
if (index >= 0 || index <= numItems - 1 )
item[index] = x;
else { /*에러 처리*/ }
}
// 원소 x가 배열 리스트의 몇 번째 원소인지 알려주기
private final int NOT_FOUND = -12345;
public int indexOf(E x) {
for (int i = 0; i < numItems; i++) {
if (((Comparable) item[i]).compareTo(x) == 0)
return i;
}
return NOT_FOUND; // not exist
}
//리스트의 총 원소수 알려주기
public int len() {
return numItems;
}
// 리스트가 비었는지 알려주기
public boolean isEmpty() {
return numItems == 0;
}
//리스트 깨끗이 비우기
public void clear() {
item = (E[]) new Object[item.length];
numItems = 0;
}
}
public class Node<E> {
public E item;
public Node<E> next;
public Node(E newItem) {
item = newItem;
next = null;
}
public Node(E newItem, Node<E> nextNode){
item = newItem;
next = nextNode;
}
}
public class LinkedList<E> implements ListInterface<E> {
private Node<E> head;
private int numItems;
public LinkedList() { // 생성자
numItems = 0;
head = new Node<>(null, null); // 더미 헤드
}
// 연결리스트에 원소 x 삽입하기
public void add(int index, E item) {
if (index >= 0 && index <= numItems) {
Node<E> prevNode = getNode(index - 1);
Node<E> newNode = new Node<>(item, prevNode.next);
prevNode.next = newNode;
numItems++;
}
}
public void append(E item) {
Node<E> prevNode = head;
while (prevNode.next != null) {
prevNode = prevNode.next;
}
Node<E> newNode = new Node<>(item, null);
prevNode.next = newNode;
numItems++;
}
//리스트의 원소 삭제하기
public E remove(int index) {
if (index >= 0 && index < numItems) {
Node<E> prevNode = getNode(index - 1);
Node<E> currNode = prevNode.next;
prevNode.next = currNode.next;
numItems--;
return currNode.item;
} else
return null;
}
public boolean removeItem(E x) {
Node<E> currNode = head; //더미헤드
Node<E> prevNode;
for (int i = 0; i < numItems; i++) {
prevNode = currNode;
currNode = currNode.next;
if (((Comparable) (currNode.item)).compareTo(x) == 0) {
prevNode.next = currNode.next;
numItems--;
return true;
}
}
return false; //NotFounded
}
// 연결리스트의 k번째 원소 알려주기
public E get(int index) {
if (index >= 0 && index < numItems)
return getNode(index).item;
else
return null; //에러 처리
}
public Node<E> getNode(int index) {
if (index >= -1 && index <= numItems - 1) {
Node<E> currNode = head; // 더미노드
for (int i = 0; i <= index; i++)
currNode = currNode.next;
return currNode;
} else {
return null;
}
}
// 연결리스트 k번째 원소를 x로 대체하기
public void set(int index, E x) {
if (index >= 0 && index < numItems) { getNode(index).item = x;}
else { /* 에러 처리 */ }
}
// 원소 x가 연결리스트의 몇 번째 원소인지 알려주기
public final int NOT_FOUND = -12345;
public int indexOf(E x) {
Node<E> currNode = head; //더미 노드
int i;
for (i = 0; i < numItems; i++) {
currNode = currNode.next;
if (((Comparable) (currNode.item)).compareTo(x) == 0)
return i;
}
return NOT_FOUND; // notFound
}
//리스트의 총 원소수 알려주기
public int len() {
return numItems;
}
//리스트가 비었는지 알려주기
public boolean isEmpty() {
return numItems == 0;
}
//리스트 깨끗이 청소하기
public void clear() {
numItems = 0;
head = new Node<>(null, null);
}
}
head가 더미 헤드 노드를 가리키도록 하는 대신 마지막 노드에 대한 레퍼런스 tail을 두고,
마지막 노드가 맨 앞의 더미 헤드 노드를 링크하는 방식
public class CircularLinkedList<E> implements ListInterface<E> {
private Node<E> tail;
private int numItems;
public CircularLinkedList() { // 생성자
numItems = 0;
tail = new Node(-1);
tail.next = tail;
}
public void add(int index, E x) { //첫 번째 원소는 0번 원소
if (index >= 0 && index <= numItems) {
Node<E> prevNode = getNode(index - 1);
Node<E> newNode = new Node<>(x, prevNode.next);
prevNode.next = newNode;
if (index == numItems)
tail = newNode;
numItems++;
}
}
public void append(E x) {
Node<E> prevNode = tail; // 더미노드
Node<E> newNode = new Node<>(x, tail.next);
prevNode.next = newNode;
tail = newNode;
numItems++;
}
public E remove(int index) {
if (index >= 0 && index <= numItems - 1) {
Node<E> prevNode = getNode(index - 1);
E rItem = prevNode.next.item;
prevNode.next = prevNode.next.next;
if (index == numItems) {
tail = prevNode;
}
numItems--;
return rItem;
} else return null;
}
public boolean removeItem(E x) {
Node<E> currNode = tail.next; // 더미헤드
Node<E> prevNode;
for (int i = 0; i < numItems; i++) {
prevNode = currNode;
currNode = currNode.next;
if (((Comparable) currNode.item).compareTo(x) == 0) {
prevNode.next = currNode.next;
numItems--;
return true;
}
}
return false; //not found
}
public E get(int index) {
if (index >= 0 && index <= numItems - 1) {
return getNode(index).item;
} else return null; // 에러
}
public void set(int index, E x) {
if (index >= 0 && index <= numItems - 1) { getNode(index).item = x; }
else { /*에러처리*/ }
}
private Node<E> getNode(int index) {
if (index >= -1 && index <= numItems - 1) {
Node<E> currNode = tail.next; //더미헤드
for (int i = 0; i <= index; i++) {
currNode = currNode.next;
}
return currNode;
} else { return null; }
}
public final int NOT_FOUND = -12345;
public int indexOf(E x) { //원소 x의 인덱스 반환
Node<E> currNode = tail.next; //더미헤드
for (int i = 0; i < numItems; i++) {
currNode = currNode.next;
if (((Comparable) (currNode.item)).compareTo(x) == 0) return i;
}
return NOT_FOUND;
}
public int len() {
return numItems;
}
public boolean isEmpty() {
return numItems == 0;
}
public void clear() {
numItems = 0;
tail = new Node(-1);
tail.next = tail;
}
}
각 노드 앞뒤로 링크되는 양방향 연결리스트는 다음노드뿐 아니라 직전 노드에 대한 링크도 가져
한 노드만 알면 앞 뒤로 자유롭게 이동가능한 연결리스트
public class BidirectionalNode<E> {
public BidirectionalNode<E> prev;
public E item;
public BidirectionalNode<E> next;
public BidirectionalNode() {
prev = next = null;
item = null;
}
public BidirectionalNode(E newItem) {
prev = next = null;
item = newItem;
}
public BidirectionalNode(BidirectionalNode<E> prevNode, E newItem, BidirectionalNode<E> nextNode) {
prev = prevNode;
next = nextNode;
item = newItem;
}
}
public class CircularDoublyLinkedList<E> implements ListInterface<E> {
private BidirectionalNode<E> head;
private int numItems;
public CircularDoublyLinkedList() { //생성자
numItems = 0;
head = new BidirectionalNode<>(null); // 더미헤드
head.next = head.prev = head;
}
public void add(int index, E x) { // 첫 원소는 0번 원소
if (index >= 0 && index <= numItems) {
BidirectionalNode<E> preNode = getNode(index - 1);
BidirectionalNode<E> newNode =
new BidirectionalNode<>(preNode, x, preNode.next);
newNode.next.prev = newNode;
preNode.next = newNode;
numItems++;
} else { /*에러처리*/ }
}
public void append(E x) {
BidirectionalNode<E> prevNode = head.prev;
BidirectionalNode<E> newNode =
new BidirectionalNode<>(prevNode, x, null);
prevNode.next = newNode;
head.prev = newNode;
numItems++;
}
public E remove(int index) {
if (index >= 0 && index <= numItems - 1) {
BidirectionalNode<E> currNode = getNode(index);
currNode.prev.next = currNode.next;
currNode.next.prev = currNode.prev;
numItems--;
return currNode.item;
} else
return null;
}
public boolean removeItem(E x) {
BidirectionalNode<E> currNode = head; // 더미 헤드
for (int i = 0; i < numItems; i++) {
currNode = currNode.next;
if (((Comparable) (currNode.item)).compareTo(x) == 0) {
currNode.prev.next = currNode.next;
currNode.next.prev = currNode.prev;
numItems--;
return true;
}
}
return false;
}
public E get(int index) {
if (index >= 0 && index < numItems) {
return getNode(index).item;
} else
return null; // 에러
}
public void set(int index, E x) {
if (index >= 0 && index < numItems) {
getNode(index).item = x;
} else { /*에러처리*/ }
}
public BidirectionalNode<E> getNode(int index) {
if (index >= -1 && index < numItems) {
BidirectionalNode<E> curNode = head;
for (int i = 0; i <= index; i++) {
curNode = curNode.next;
}
return curNode;
} else
return null;
}
public final int NOT_FOUND = -12345;
public int indexOf(E x) {
BidirectionalNode<E> currNode = head;
for (int i = 0; i < numItems; i++) {
currNode = currNode.next;
if (((Comparable) (currNode.item)).compareTo(x) == 0)
return i;
}
return NOT_FOUND;
}
public int len() {
return numItems;
}
public boolean isEmpty() {
return numItems == 0;
}
public void clear() {
numItems = 0;
head = new BidirectionalNode<>(null);
head.next = head.prev = head;
}
}
저도 이책으로 공부중인데 궁금한게
IntegerArrayList에서 add메소드 보시면
if (numItems >= item.length || ...) {
이 코드 보시면 좀 이상하지 않나요?
가장 처음 add()를 실행한다고 했을때 add(0, 1)을 실행한다고 할게요
그럼 numItems >= item.length 이 조건에 값을 대입하면 0 >= 0이 되어 참이 되니까 에러처리가 되는거 아닌가요?
부호를 >= 이 아닌 >으로 해야 되는게 아닐까 하는 생각이 드네요