쉽게 배우는 자료구조 - Chap5.

KanuKim97·2023년 1월 10일
0

Data Structure with Java

목록 보기
2/6

리스트

사전적 의미

'줄 세워져 있는 데이터' 또는 '쭉 늘어선 데이터'를 의미한다.

리스트의 작업 (ADT 리스트)

i번째 자리에 원소 x를 삽입한다.
i번째 원소를 삭제한다.
원소 x를 삭제한다.
i번째 원소를 알려준다.
원소 x가 몇 번째 원소인지 알려준다.
리스트의 사이즈(원소의 총 수)를 알려준다.

자바는 언어 자체에서 리스트를 기본 자료구조로 제공하지 않고 java.util 패키지에서 제공한다.

리스트의 구현 (2가지 방법)

1. 원소를 연속된 공간에 존재하는 배열로 배치하는 방법

2. 링크를 이용해 원소들을 연결하는 방법

배열을 이용한 리스트 구현은 가장 단순한 구현 방법으로, 메모리의 연속된 공간에서 데이터를 관리한다.
이 방법은 이름과 크기만 정하면 되므로 편리하지만 리스트에 원소가 얼마나 들어올지 예상하기 힘들어 배열을 사용하는 경우 충분한 공간을 확보해야 하는데, 이 작업은 공간 낭비가 심하다.
하지만 배열 방식은 단순하고 효율성이 높아 리스트를 구현하기 좋다.
연결 리스트는 배열의 공간 낭비를 피할 수 있는 자료구조이다.
원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따른다.

배열 리스트

각 필드와 작업의 의미

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;
    }
}

연결리스트

Node.java

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;
    }
}

LinkedList.java

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);
    }

}

연결리스트의 확장

1. 원형 연결리스트

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;
    }
}

2. 양방향 연결 리스트

각 노드 앞뒤로 링크되는 양방향 연결리스트는 다음노드뿐 아니라 직전 노드에 대한 링크도 가져
한 노드만 알면 앞 뒤로 자유롭게 이동가능한 연결리스트

양방향 노드

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;
    }
}
profile
천방지축 개발자

1개의 댓글

comment-user-thumbnail
2023년 1월 18일

저도 이책으로 공부중인데 궁금한게
IntegerArrayList에서 add메소드 보시면
if (numItems >= item.length || ...) {
이 코드 보시면 좀 이상하지 않나요?
가장 처음 add()를 실행한다고 했을때 add(0, 1)을 실행한다고 할게요
그럼 numItems >= item.length 이 조건에 값을 대입하면 0 >= 0이 되어 참이 되니까 에러처리가 되는거 아닌가요?
부호를 >= 이 아닌 >으로 해야 되는게 아닐까 하는 생각이 드네요

답글 달기