자바(Java): 양쪽 연결 리스트(Doubly Linked List; 더블 링크드 리스트) [자바 공식 제공 & 알고리즘 학습용 예제]

연결 리스트 (자바 공식 제공)

ArrayList()와 사용법은 거의 같습니다. 다만 내부 동작 방식이 다릅니다.

package blog.dblinkedlist;

import java.util.LinkedList;
import java.util.List;

public class LinkedListTest {
  
  public static void main(String[] args) {
    List<Object> list = new LinkedList<>();
    for(int i = 1; i <= 12; i++) {
      list.add(i);
    }
    
    // 인덱스 바로 뒤에 삽입(0부터 시작)
    list.add(0, "★0★");
    list.add(3, "★3.5★");
    
    // 인덱스로 삭제
    list.remove(8);
    
    // 오브젝트로 삭제(값이 10인 Object를 찾아 삭제)
    list.remove((Object)10);
    
    // get()의 인덱스도 0부터 시작
    System.out.println("index 3: " + list.get(3));
    System.out.println("size: " + list.size());
    System.out.println("list:" + list);
  }
  
}

양쪽 연결 리스트 (알고리즘 학습용 예제)

	package blog.dblinkedlist;

	public class Node {
	private Object data;
	private Node prev, next;

	// Constructor

	public Node(Object data) {
	this.data = data;
	}

	public Node(Object data, Node prev) {
	this.data = data;
	this.prev = prev;
	}

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

	// Setter and Getter

	public Object getData() {
	return data;
	}

	public void setData(Object data) {
	this.data = data;
	}

	public Node getPrev() {
	return prev;
	}

	public void setPrev(Node prev) {
	this.prev = prev;
	}

	public Node getNext() {
	return next;
	}

	public void setNext(Node next) {
	this.next = next;
	}

	// toString

	@Override
	public String toString() {
	return "Node [data=" + data + ", prev=" + prev + ", next=" + next + "]";
	}

	}

view raw

Node.java

hosted with ❤ by GitHub

	package blog.dblinkedlist;

	public class NodeMgmt {

	private Node head, tail;

	public NodeMgmt(Object data) {
	this.head = new Node(data);
	this.tail = this.head;
	}

	public Node getHead() {
	return head;
	}

	public void setHead(Node head) {
	this.head = head;
	}

	public Node getTail() {
	return tail;
	}

	public void setTail(Node tail) {
	this.tail = tail;
	}

	// 연결 리스트의 맨 마지막에 노드 추가

	public void insert(Object data) {
	if(this.head == null) {
	this.head = new Node(data);
	this.tail = this.head;
	} else {
	Node node = this.head;
	while(node.getNext() != null) {
	node = node.getNext();
	}
	Node newNode = new Node(data);
	node.setNext(newNode);
	newNode.setPrev(node);
	this.tail = newNode;
	}
	}

	// 연결 리스트 순회

	public void desc() {
	Node node = this.head;
	while(node != null) {
	System.out.println("node: " + node.getData());
	node = node.getNext();
	}
	}

	// 노드의 헤드로부터 노드 찾기

	public Node searchFromHead(Object data) {
	Node node = this.head;
	while(node != null) {
	if(node.getData().equals(data)) {
	return node;
	} else {
	node = node.getNext();
	}
	}
	return null;
	}

	// 노드의 테일로부터 노드 찾기

	public Node searchFromTail(Object data) {
	Node node = this.tail;
	while(node != null) {
	if(node.getData().equals(data)) {
	return node;
	} else {
	node = node.getPrev();
	}
	}
	return null;
	}

	public boolean insertBefore(Object data, Object beforeData) {
	if(this.head == null) {
	this.head = new Node(data);
	this.tail = this.head;
	return true;
	} else {
	Node node = this.tail; // ###
	while(!node.getData().equals(beforeData)) {
	node = node.getPrev();
	if(node == null) {
	return false;
	}
	}
	Node newNode = new Node(data);
	Node beforeNewNode = node.getPrev();
	// 이전 노드의 next 포인터 변경
	beforeNewNode.setNext(newNode);
	// newNode의 양방향 포인터 설정
	newNode.setPrev(beforeNewNode);
	newNode.setNext(node);
	// 기존 노드의 prev 포인터를 새 노드로 변경
	node.setPrev(newNode);

	return true;

	}
	}

	public boolean insertAfter(Object data, Object afterData) {
	if(this.head == null) {
	this.head = new Node(data);
	this.tail = this.head;
	return true;
	} else {
	Node node = this.head; // ###
	while(!node.getData().equals(afterData)) {
	node = node.getNext();
	if(node == null) {
	return false;
	}
	}
	Node newNode = new Node(data);
	Node afterNewNode = node.getNext();
	// 기존 존재하던 노드의 prev 포인터 변경
	afterNewNode.setPrev(newNode);
	// newNode의 양방향 포인터 설정
	newNode.setPrev(node);
	newNode.setNext(afterNewNode);
	// 기존 노드의 next 포인터를 새 노드로 변경
	node.setNext(newNode);

	return true;

	}
	}

	}

view raw

NodeMgmt.java

hosted with ❤ by GitHub

	package blog.dblinkedlist;

	public class NodeMgmtTest {

	public static void main(String[] args) {
	System.out.println("==== Node Test ====");
	// 더블 연결 리스트 생성 및 노드 삽입 테스트
	NodeMgmt dblLinkedList1 = new NodeMgmt(10);
	dblLinkedList1.insert(20);
	for(int i = 30; i <= 100; i += 10) {
	dblLinkedList1.insert(i);
	}
	dblLinkedList1.desc();

	System.out.println("\n==값을 통해 노드 찾기==");

	Node tail = dblLinkedList1.getTail();
	System.out.println(tail.getData());

	// 노드30을 헤드로부터 찾음
	Node node30 = dblLinkedList1.searchFromHead(30);
	System.out.println(node30.getData());

	// 노드80을 테일로부터 찾음
	Node node80 = dblLinkedList1.searchFromTail(80);
	System.out.println(node80.getData());

	System.out.println("\n==노드75를 80 전에 삽입==");

	// 노드75를 80 전에 삽입
	boolean node75i = dblLinkedList1.insertBefore("==75==", 80);
	System.out.println(node75i);
	dblLinkedList1.desc();

	System.out.println("\n==노드35를 30 앞에 삽입==");

	// 노드35를 30 앞에 삽입
	boolean node35i = dblLinkedList1.insertAfter("==35==", 30);
	System.out.println(node35i);
	dblLinkedList1.desc();


	}

	}