[자료구조] LinkeList 자바로 구현하기

생성일: September 24, 2020

7 분 소요

용어 설명

HEAD - Linked List에서 누가 첫번째 노드인가를 알려줌
TAIL - 제일 끝 노드는 누구인지 알려줌 (유지 할수도, 안할수도 있음)
SIZE - 현재 몇 개의 엘리먼트가 리스트에 있는가
Data field - 값
Link field - 다음 리스트에 대한 레퍼런스값을 가진 변수
node / vertex / element - 객체

1. 객체 생성

LinkedList 클래스와 Main 클래스 생성

LinkedList를 만들 클래스와 실행 클래스를 생성한다.

Main.java

package list.linkedlist.implementation;

public class Main {

	public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
	}

}

LinkedList.java

package list.linkedlist.implementation;

public class LinkedList {
	private Node head;// 누가 첫번재 노드인가
	private Node tail;// 누가 마지막 노드인가
	private int size = 0;
	private class Node{ // 내부 객체 정의 (노드)
		//1. 데이터 저장 //2. 다음이 누구인지 알려줌
		private Object data; // 노드가 저장할 데이터
		private Node next; // 다음 노드에 대한 정보
		// 초기화
		public Node(Object input) {//input : 노드의 값
			this.data = input;
			this.next = null; // 객체 생성시엔 다음이 누군지 모름
		}
		public String toString() {
			return String.valueOf(this.data);
		}
	}
}

2. 데이터 추가 - addFirst

addFirst메소드를 생성

Main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addFirst(30);
		numbers.addFirst(20);
		numbers.addFirst(10);
	}

addFirst()메소드 구현하기

LinkedList.java

public void addFirst(Object input) {
		Node newNode = new Node(input); // data = 30, next = null
		newNode.next = head;
		head = newNode; // LinkedList에서 내부적으로 유지하고 있는 멤버변수 head에 새로 만든 newNode를 지정
		size++; // 0 -> 1
		if(head.next == null) { // 다음 노드가 존재하지 않는다 == 혼자 있다
			tail = head; // 노드가 하나라면, head가 곧 tail이다
		}
	}

Node를 생성하는 메소드 - 새로 만든 노드를 가장 첫번째 노드를 가리키는 head에 값을 넣는다

LinkedList.java 전체코드

package list.linkedlist.implementation;

public class LinkedList {
	private Node head;// 누가 첫번재 노드인가
	private Node tail;// 누가 마지막 노드인가
	private int size = 0;
	private class Node{ // 내부 객체 정의 (노드)
		//1. 데이터 저장 //2. 다음이 누구인지 알려줌
		private Object data; // 노드가 저장할 데이터
		private Node next; // 다음 노드에 대한 정보
		// 초기화
		public Node(Object input) {//input : 노드의 값
			this.data = input;
			this.next = null; // 객체 생성시엔 다음이 누군지 모름
		}
		public String toString() {
			return String.valueOf(this.data);
		}
	}
	public void addFirst(Object input) {
		Node newNode = new Node(input); // data = 30, next = null
		newNode.next = head;
		head = newNode; // LinkedList에서 내부적으로 유지하고 있는 멤버변수 head에 새로 만든 newNode를 지정
		size++;
		if(head.next == null) { // 다음 노드가 존재하지 않는다 == 혼자 있다
			tail = head;
		}
	}
}

3. 데이터 추가 - addLast

main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
	}

LinkedList.java

public void addFirst(Object input) {
		Node newNode = new Node(input); // data = 30, next = null
		newNode.next = head;
		head = newNode; // LinkedList에서 내부적으로 유지하고 있는 멤버변수 head에 새로 만든 newNode를 지정
		size++;
		if(head.next == null) { // 다음 노드가 존재하지 않는다 == 혼자 있다
			tail = head;
		}
	}
	
	public void addLast(Object input) {
		Node newNode = new Node(input);
		if(size == 0) { // 만약 데이터가 없다면
			addFirst(input); //데이터를 앞쪽에 넣든 뒤에 넣든 상관 없다
		}else { //데이터가 이미 존재한다면
			tail.next = newNode;
			tail = newNode;
			size++;
		}
	}

4. Node

내부적으로 사용할 Node 메서드를 만든다.

public Node node(int index) {//Node 인스턴스를 리턴
		
	}

메인메소드에서 System.out.println(numbers.node(0));를 실행하면 10을 가지고 있는 노드 객체가 리턴된다.

어떤 엘리먼트를 가져오고 싶다면? ⇒ 그 리스트의 첫번째 리스트(노드)를 찾아가야 한다. → 헤드

main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		System.out.println(numbers.node(2));
	}

만약 2번 인덱스의 노드값을 구하고 싶다면?

LinkedList.java

public Node node(int index) {//Node 인스턴스를 리턴
		Node x = head;
		x = x.next;
		x = x.next;
		return x;
	}

x = x.next; ← 이 부분이 index만큼 반복한다는 것을 볼 수 있다.

public Node node(int index) {//Node 인스턴스를 리턴
		Node x = head;
		for(int i=0; i < index; i++) {
			x = x.next;
		}
		return x;
	}

리턴값 자체가 Node이기 때문에 내부적으로 사용하고 있는 Node객체를 직접 리턴하면 안된다(내부적으로 쓰이는 부품이 외부에 노출되면 안된다)

⇒ public 없애기

5. 특정한 위치에 원하는 값 끼워넣기 - add

1번 인덱스 위치에 15값을 넣는 add(1, 15)메소드 생성 ⇒ 20이 뒤로 밀리고, 10과 20 사이에 15가 들어간다

main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		numbers.add(2, 25); // index 2의 위치(20과 30 사이)에 25를 넣겠다.
	}

LinkedList.java

public void add(int k, Object input) { // k : 추가하려는 노드의 리스트 상에서의 인덱스값
		if(k == 0) {
			addFirst(input); //첫번째 위치로 들어온다
		} else { 
			Node temp1 = node(k-1);
			Node temp2 = temp1.next;
			Node newNode = new Node(input); // 새로운 노드 생성
			temp1.next = newNode;
			newNode.next = temp2;
			size++;
			if(newNode.next == null) {
				tail = newNode;
			}
		}
		
	}

6. 확인하기 - toString

System.out.println(numbers);

⇒ 결과값 : list.linkedlist.implementation.LinkedList@28a418fc

잘 알아볼 수 있도록 toString을 이용하기

LinkedList.java

public String toString() {
		// 만약 데이터가 없다면 [] 출력
		if(head == null) {
			return "[]";
		}
		// 리스트로 순차적인 작업인 처리를 한다면 
		// 제일먼저 "head가 누군지"부터 찾아야 한다!
		Node temp = head;
		String str = "[";
		
		while(temp.next != null) {
			str += temp.data + ", ";
			temp = temp.next;
		}
		str += temp.data; // 마지막은 next가 없기 때문에 값을 수동으로 추가한다
		
		return str +"]";
	}

리스트 안에 데이터가 없다면 [] 괄호만 출력되도록 한다
데이터가 있다면 head부터 순차적으로 출력한다

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		numbers.add(1, 15);
		System.out.println(numbers);
	}

결과값 ⇒ [10, 15, 20, 30]

7. removeFirst

리스트의 첫번째 값을 삭제하는 numbers.removeFirst()를 구현한다

linkedList.java

public Object removeFirst() {
		// 노드를 탐색해야하기 때문에 head값을 일단 찾아 temp에 넣는다
		Node temp = head;
		// head는 삭제될 거니까 다음 노드로 head를 옮긴다
		head = head.next;
		// 자바의 컬렉션에서 삭제하는 값을 리턴하듯, 
		// 우리도 삭제될 데이터 값을 returnData에 담아 리턴한다. 
		Object returnData = temp.data;
		temp = null;
		size--;
		return returnData;
	}

main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		System.out.println(numbers.removeFirst()); // 잘 됐는지 확인
		System.out.println(numbers);
	}

결과값 ⇒

10 [20, 30]

삭제한 데이터값인 10과 삭제된 후의 리스트값인 [20,30]이 출력되었다.

8. remove, removeLast

remove

특정한 위치에 있는 엘리먼트를 삭제한다.

삭제하려는 노드의 이전 노드를 알아야 한다. 삭제될 노드의 이전 노드가 next로 삭제하려는 노드의 다음 노드를 가리켜야 하기 때문에.
삭제하려는 노드 k -1을 알아내서 그걸 temp의 값으로 지정한다

linkedList.java

public Object remove(int k) {// k는 인덱스 값
		if(k == 0) {
			return removeFirst();
		}
		Node temp = node(k-1);
		Node todoDeleted = temp.next; // 삭제하려는 노드
		temp.next = temp.next.next;
		Object returnData = todoDeleted.data;
		if(todoDeleted == tail) {// 삭제하려는 노드가 마지막 노드라면,
			tail = temp; // 삭제하려는 노드의 이전 노드이다
		}
		todoDeleted = null;
		size--;
		return returnData;
	}

main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(5);		
		numbers.addLast(10);
		numbers.addLast(15);		
		numbers.addLast(20);
		numbers.addLast(30);
		System.out.println(numbers.remove(2)); // 잘 됐는지 확인
		System.out.println(numbers);
	}

결과값 ⇒

15 [5, 10, 20, 30]

removeLast

public Object removeLast() {
		return remove(size-1);
	}

위에서 만든 remove()를 이용해서 size-1을 넣어준다
remove를 쓰면 앞에서부터 하나씩 찾아서 마지막까지 가야하는데, 어차피 tail에 마지막 노드의 정보가 들어있으니 그것만 삭제하면 안되나? → 안됨. 부족함
- 그 이전 노드의 next값을 지워주어야지만 삭제된 효과가 있다. 즉, temp(이전 노드)를 알아야 한다!!
- 그래서 가장 마지막 노드를 지운다는건 최악의 경우이다. (만약 데이터가 천만개라면 속도가 엄청나게 늦어질것임)
- 반면, ArrayList는 내부적으로 index를 가지고 있다 ⇒ 배열의 마지막 인덱스값만 가지고 있으면 괭장히 빠르게 삭제를 처리할 수 있다.

main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(5);		
		numbers.addLast(10);
		numbers.addLast(15);		
		numbers.addLast(20);
		numbers.addLast(30);
		System.out.println(numbers.removeLast()); // 잘 됐는지 확인
		System.out.println(numbers);
	}

결과값⇒

30 [5, 10, 15, 20]

9. size, get

size() : 가지고 있는 엘리먼트의 갯수 구하기
```
  public int size() {
  		return size;
  	}
```
삭제하거나 추가할 때 마다 사이즈 값을 갱신해왔기 때문에 size값을 그냥 호출하면 된다.
get(index) : 특정한 위치에 있는 엘리먼트를 가져올 때 사용
Main.java

System.out.println(numbers.get(1));

LinkedList.java

  public Object get(int k) {
  		Node temp = node(k); // 인덱스 값을 그대로 준다
  		return temp.data;
  	}

10. indexOf

특정한 데이터가 어떤 위치에 존재하는가를 검색.

Main.java

public static void main(String[] args) {
		LinkedList numbers = new LinkedList(); //링크드 리스트 인스턴스화
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		System.out.println(numbers.indexOf(30)); // 2를 리턴
	}

LinkedList.java

public int indexOf(Object data) {
		Node temp = head;
		// 찾고자 하는 노드가 나올때까지 하나하나 검색
		int index = 0; // 찾고자하는 노드의 위치정보
		while(temp.data != data) { // temp에 저장된 데이터값과 검색하고자 하는 데이터값이 같지 않으면 계속 검색
			temp = temp.next; //다음 노드를 찾을 수 있도록
			index++;
			if(temp == null) {// 끝 노드에 도달했다면
				return -1;// 검색 종료
			}
		}
		return index;
	}

결과값 ⇒ 2

Twitter Facebook LinkedIn

Grey

[자료구조] LinkeList 자바로 구현하기

용어 설명

1. 객체 생성

LinkedList 클래스와 Main 클래스 생성

2. 데이터 추가 - addFirst

3. 데이터 추가 - addLast

4. Node

5. 특정한 위치에 원하는 값 끼워넣기 - add

6. 확인하기 - toString

잘 알아볼 수 있도록 toString을 이용하기

7. removeFirst

8. remove, removeLast

remove

removeLast

9. size, get

10. indexOf

공유하기

댓글남기기

참고

이력서 기반으로 ChatGPT와 나의 강점과 약점 분석하고 계획하기

기업이 원하는 PM의 조건은 뭘까

[항해99 취업 리부트 코스 학습일지][day21] 질문 대폭발의 날

[항해99 취업 리부트 코스 학습일지][day20] 어제보단 나은 하루