[자료구조] 리스트 (List) 구현 (Java)

 

LinkedList - Node들의 구조

📍리스트(List) 란?

순서를 가지도록 데이터를 나열한 것
리스트에서는 각각의 요소를 노드라고 한다.
노드는 데이터와 다음 노드의 위치를 저장한다.

---

📍단일 연결리스트(List) 의 구현

🐾  클래스 구조  

 

1.  노드 클래스
데이터와 노드를 저장할 수 있는 클래스

package list;

public class Node {
    Integer data;
    Node next;

    public Node(Integer data, Node next) {
        this.data = data;
        this.next = next;
    }
}

 

---

  2. 리스트 클래스
head  : 맨 처음 노드를 저장한다. 

리스트 클래스의 메소드는 다음과 같다. 

 

🐾생성자

head에 null을 저장한다. 

    public LinkedList() {
        this.head = null;
    }

 

🐾 insertFirst(x); 맨 처음에 데이터 x를 추가

insertFirst()

데이터 값을 매개변수로 전달 받는다. 

노드 객체 생성(노드의 next에는 기존 head를 저장)

head에 방금 생성한 노드를 저장

    void insertFirst(int x){
        Node node = new Node(x, head);
        head = node;
    }

 

🐾 insertLast(x); 맨 마지막에 데이터 x를 추가

insertLast()

데이터 값을 매개변수로 전달 받는다. 

head가 null이면 insertFirst를 실행한다. 

노드 객체 생성(노드의 next에는 null 저장)

마지막 노드였던 current의 next에는 방금 생성한 노드를 저장

    void insertLast(int x){
        if(head == null) this.insertFirst(x);
        else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            Node node = new Node(x, null);
            current.next = node;
        }
    }

 

🐾 inserIndex(index, x); 원하는 index에 데이터 x를 추가

insertIndex(2,data)

데이터를 삽입할 인덱스와 데이터 값을 매개변수로 전달 받는다. 

노드 객체 생성(노드의 next에는 원하던 index의 노드를 저장)

원하던 index의 전 노드인 current의 next에는 방금 생성한 노드를 저장

    void insertIndex(int index, int x){
        Node current = head;
        //head가 인덱스 0
        for (int i = 1; i < index; i++) {
            current = current.next;
        }
        Node node = new Node(x, current.next);
        current.next = node;
    }

 

🐾 display(); 현재 노드들을 모두 출력

    void display(){
        Node current = head;
        while(true){
            System.out.printf("[%d] ",current.data);
            if(current.next == null) break;
            current = current.next;
        }
        System.out.println();
    }

 

리스트 삭제 메소드

 

🐾 removeFirst(); 맨 처음 노드를 삭제

 

🐾removeLast(); 맨 마지막 노드를 삭제

 

🐾 removeIndex(index); 원하는 인덱스의 노드를 삭제

---

📍전체 코드

LinkedList.java

package list;

public class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    void insertFirst(int x){
        Node node = new Node(x, head);
        head = node;
    }

    void insertLast(int x){
        if(head == null) this.insertFirst(x);
        else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            Node node = new Node(x, null);
            current.next = node;
        }
    }

    void insertIndex(int index, int x){
        Node current = head;
        //head가 인덱스 0
        for (int i = 1; i < index; i++) {
            current = current.next;
        }
        Node node = new Node(x, current.next);
        current.next = node;
    }

    void display(){
        Node current = head;
        while(true){
            System.out.printf("[%d] ",current.data);
            if(current.next == null) break;
            current = current.next;
        }
        System.out.println();
    }
}

 

LinkedListMain.java

package list;

public class LinkedListMain {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        ll.insertFirst(10);
        ll.insertFirst(20);
        ll.insertFirst(30);
        ll.display();

        ll.insertLast(40);
        ll.insertLast(50);
        ll.display();

        ll.insertIndex(3, 60);
        ll.display();
    }
}

 

 

실행 결과