자료구조 :: JAVA를 이용한 단일 연결 리스트 LinkedList 구현하기

신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

연결리스트

연결리스트 종류에는 2가지가 있다.

'단일 연결 리스트'와 '이중 연결 리스트'가 있다.

'단일 연결 리스트' 에 대해 알아본다.

단일 연결 리스트 (Linked List)

단일 연결리스트는 기본적으로 'Node'로 구성된다.

한 노드 안에는 다음 노드의 주소를 저장하기 위한 변수(Next)와

데이터를 저장하기 위한 변수(Data)를 가지게 된다.

노드의 종류는 2가지로 나눠진다.

헤드 노드와 일반적인 노드

헤드노드는 제일 첫번째의 노드로, '연결리스트'의 기준점이 될 뿐 데이터를 저장하진 않는다.

헤드노드를 제외한 나머지 노드를 이용해서 데이터를 저장한다.

노드의 명칭만 다르게 부를 뿐이고, 똑같은 'Node class'를 사용해서 구현한다.

아래 코드를 통해 더 자세히 알아본다.

구현단계

노드 클래스를 만들고 헤드노드를 생성한다.

public class MyLinkedList {
 
    // 헤드 노드 생성
    private Node headNode;
    private int  size;
 
    private class Node {
 
        private Node   nextNode;
        private Object data;
 
        Node() {
        }
 
        Node(Object data) {
            // 새로 추가한 node의 nextNode 초기값은 null 로 설정
            this.nextNode = null;
            this.data = data;
        }
    }
}

데이터 추가하기

    // add Node, addLast
    public void add(int index, Object data) {
        if(index <0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
        
        Node newNode = new Node(data);
        Node preNode = getNode(index-1);
        newNode.nextNode = preNode.nextNode;
        preNode.nextNode = newNode;
        size++;
    }
    public void addLast(Object data) {
        add(size-1, data);
    }

add() 메소드는 원하는 위치에 데이터를 넣는 메소드이다.

addLast() 메소드는 '연결리스트'의 마지막 위치에 데이터를 넣는 메소드이다.

    // 첫번째 노드에 데이터를 저장하기 위한 Method
    public void addFirst(Object data) {
 
        // 새로운 Node 생성
        Node newNode = new Node(data);
        // 새로운 Node의 next Node의 주소값
        newNode.nextNode = headNode.nextNode;
        // headNode의 next Node의 주소값 = new Node의 주소값
        headNode.nextNode = newNode;
        // size 증가
        size++;
    }

addFirst() 메소드는 맨 처음 위치에 데이터를 넣는 메소드이다.

새로운 노드가 들어오게 되면,

기존 노드의 연결을 끊는다.

그리고 새로운 노드와 연결을 잇는다.

데이터 삭제

    // 첫번째 Node 삭제
    public Object removeFirst() {
        Node node = headNode.nextNode;
        headNode.nextNode = node.nextNode;
        Object result = node.data;
        node = null;
        size--;
        return result;
    }

removeFirst() 메소드는 맨 처음에 위치한 데이터를 삭제하고 그 값을 반환하는 메소드이다.

노드를 삭제하고 나면 '제거된 노드의 이전 노드'와 '제거된 노드의 다음 노드'를 연결시켜준다.

    // 특정한 Node 삭제
    public Object remove(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
    
        if(index == 0) {
            return removeFirst();
        }else {    
            Node preNode = getNode(index-1);
            Node removeNode = preNode.nextNode;
            Node postNode = removeNode.nextNode;
            preNode.nextNode = postNode;
            Object result = removeNode.data;
            removeNode = null;
            size--;
            return result;
        }
        
    }

remove() 메소드는 원하는 위치의 데이터를 삭제하고 그값을 반환하는 메소드이다.

제거할 노드와 앞,뒤 노드의 연결을 해제하고,

새롭게 앞, 뒤 노드간의 연결을 만든다.

값 가져오기, 출력하기

    // 특정한 Node의 data값 가져오기
    public Object get(int index) {
        return getNode(index).data;
    }
 
    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        } else {
            Node node = headNode.nextNode;
            for(int i=0; i < index; i++) {
                node = node.nextNode;
            }
            return node;
        }
    }

인덱스를 이용하여, 특정한 위치의 데이터를 가지고 온다.

    // size 가져오기
    public int size() {
        return size;
    }

    // 모든 데이터 출력
    public String toString() {
        StringBuffer result = new StringBuffer("[");
        Node node = headNode.nextNode;
        if(node == null) {
            result.append("No Data");
        }else{
            result.append(node.data);
            node = node.nextNode;
            while(node != null) {
                result.append(", ");
                result.append(node.data);
                node = node.nextNode;
            }
        }
        result.append("]");
        return result.toString();
    }

리스트의 모든 데이터를 출력한다.

완성된 '단일 연결 리스트'의 전체 코드

public class MyLinkedList {
 
    private Node headNode;
    private int  size;
 
    public MyLinkedList() {
        // 생성시 Head Node 생성
        // head 는 일반적으로 데이터를 저장하지 않음
        // 첫번째 노드 주소를 가르키기 위한 용도
        headNode = new Node();
        size = 0;
    }
 
    // 첫번째 노드에 데이터를 저장하기 위한 Method
    public void addFirst(Object data) {
 
        // 새로운 Node 생성
        Node newNode = new Node(data);
        // 새로운 Node의 next Node의 주소값
        newNode.nextNode = headNode.nextNode;
        // headNode의 next Node의 주소값 = new Node의 주소값
        headNode.nextNode = newNode;
        // size 증가
        size++;
    }
 
    // 특정한 Node의 data값 가져오기
    public Object get(int index) {
        return getNode(index).data;
    }
 
    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        } else {
            Node node = headNode.nextNode;
            for(int i=0; i < index; i++) {
                node = node.nextNode;
            }
            return node;
        }
    }
 
    // add Node, addLast
    public void add(int index, Object data) {
        if(index <0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
        
        Node newNode = new Node(data);
        Node preNode = getNode(index-1);
        newNode.nextNode = preNode.nextNode;
        preNode.nextNode = newNode;
        size++;
    }
    public void addLast(Object data) {
        add(size-1, data);
    }
    
    // 첫번째 Node 삭제
    public Object removeFirst() {
        Node node = headNode.nextNode;
        headNode.nextNode = node.nextNode;
        Object result = node.data;
        node = null;
        size--;
        return result;
    }
    
    // 특정한 Node 삭제
    public Object remove(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
    
        if(index == 0) {
            return removeFirst();
        }else {    
            Node preNode = getNode(index-1);
            Node removeNode = preNode.nextNode;
            Node postNode = removeNode.nextNode;
            preNode.nextNode = postNode;
            Object result = removeNode.data;
            removeNode = null;
            size--;
            return result;
        }
        
    }
    
    // size 가져오기
    public int size() {
        return size;
    }
    
    // 모든 데이터 출력
    public String toString() {
        StringBuffer result = new StringBuffer("[");
        Node node = headNode.nextNode;
        if(node == null) {
            result.append("No Data");
        }else{
            result.append(node.data);
            node = node.nextNode;
            while(node != null) {
                result.append(", ");
                result.append(node.data);
                node = node.nextNode;
            }
        }
        result.append("]");
        return result.toString();
    }
    
    
    private class Node {
 
        private Node   nextNode;
        private Object data;
 
        Node() {
        }
 
        Node(Object data) {
            // 새로 추가한 node의 next 초기값은 null 로 설정
            this.nextNode = null;
            this.data = data;
        }
    }
    
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        
        list.addFirst(500);
        list.addFirst(400);
        list.addFirst(300);
        list.addFirst(200);
        list.addFirst(100);
        System.out.println(list.toString()); // 100 200 300 400 500
        
        list.add(1, 150);
        System.out.println(list.toString()); // 100 150 200 300 400 500
        
        list.remove(1);
        System.out.println(list.toString()); // 100 200 300 400 500
        System.out.println(list.size()); // 5
        
        list.removeFirst();
        System.out.println( list.toString()); // 200 300 400 500
        
        System.out.println(list.get(2)); // 400
    }
}

실행결과

[100, 200, 300, 400, 500]

[100, 150, 200, 300, 400, 500]

[100, 200, 300, 400, 500]

[200, 300, 400, 500]

400

저작자표시 비영리

'Algorithm' 카테고리의 다른 글

자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현) (20)	2018.04.28
자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현) (8)	2018.04.28
자료구조 :: 버블정렬 Bubble sort (c/c++ 구현) (6)	2018.04.28
자료구조 :: 선택정렬 Selection sort (c/c++ 구현) (2)	2018.04.28
자료구조 :: JAVA를 이용한 이중 연결 리스트 (Doubly Linked List) 구현하기 (6)	2018.04.19