Java数据结构之链表相关知识总结

一、链表

1.1 概述

链表是真正动态的数据结构，最简单的动态数据结构，基本用于辅助组成其他数据结构。

数据存储在“节点”（Node）中

优点：真正的动态，不需要处理固定容量的问题
缺点：丧失了随机访问的能力

1.2 链表使用的基本功能

定义Node节点

private class Node{
       public E e;
       public Node next;

public Node(E e, Node next){
           this.e = e;
           this.next = next;
       }

public Node(E e){
           this(e, null);
       }

public Node(){
           this(null,null);
       }

@Override
       public String toString() {
           return e.toString();
       }
   }

向链表中添加元素

具体代码实现：

//向链表中间添加元素
   //在链表的index(0-based)位置添加新的元素e
   public void add(int index, E e){
       if(index < 0 || index > size)
           throw new IllegalArgumentException("Add failed.Illeagl failed.");
       Node prev = dummyHead;
       for (int i = 0; i < index; i++) {
           prev = prev.next;
       }
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;

prev.next = new Node(e, prev.next);
       size++;
   }

向链表中删除元素

具体代码实现：

//链表中删除index(0-based)位置的元素，返回删除的元素
   public E remove(int index){
       if(index < 0 || index >= size)
           throw new IllegalArgumentException("Remove failed.Illeagl failed.");
       Node pre = dummyHead;
       for (int i = 0; i < index; i++) {
           pre = pre.next;
       }
       Node retNode = pre.next;
       pre.next = retNode.next;
       retNode.next = null;
       size--;

return retNode.e;
   }

链表功能的实现及测试类

public class LinkedList<E> {
   private class Node{
       public E e;
       public Node next;

public Node(E e, Node next){
           this.e = e;
           this.next = next;
       }

public Node(E e){
           this(e, null);
       }

public Node(){
           this(null,null);
       }

@Override
       public String toString() {
           return e.toString();
       }
   }

private Node dummyHead;
   private int size;

public LinkedList(){
       dummyHead = new Node(null, null);
       size = 0;
   }

//获取链表中的元素个数
   public int getSize(){
       return size;
   }

//返回链表是否为空
   public boolean isEmpty(){
       return size == 0;
   }

//向链表头添加元素
   public void addFirst(E e){
//        Node node = new Node(e);
//        node.next = head;
//        head = node;

add(0, e);
   }

//向链表中间添加元素
   //在链表的index(0-based)位置添加新的元素e
   public void add(int index, E e){
       if(index < 0 || index > size)
           throw new IllegalArgumentException("Add failed.Illeagl failed.");
       Node prev = dummyHead;
       for (int i = 0; i < index; i++) {
           prev = prev.next;
       }
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;

prev.next = new Node(e, prev.next);
       size++;
   }

//在链表的末尾添加新的元素e
   public void addLast(E e){
       add(size, e);
   }

//获得链表的第index(0-based)个位置的元素
   //在链表中不是一个常用的操作
   public E get(int index){
       if(index < 0 || index > size)
           throw new IllegalArgumentException("Add failed.Illeagl failed.");
       Node cur = dummyHead.next;
       for (int i = 0; i < index; i++) {
           cur = cur.next;
       }
       return cur.e;
   }

//获得链表的第一个元素
   public E getFirst(){
       return get(0);
   }

//获得链表的最后一个元素
   public E getLast(){
       return get(size - 1);
   }

//修改链表的第index(0-based)个位置的元素
   //在链表中不是一个常用的操作
   public void set(int index, E e){
       if(index < 0 || index > size)
           throw new IllegalArgumentException("Add failed.Illeagl failed.");
       Node cur = dummyHead.next;
       for (int i = 0; i < index; i++) {
           cur = cur.next;
       }
       cur.e = e;
   }

//查找链表中是否有元素e
   public boolean contains(E e){
       Node cur = dummyHead.next;
       while(cur != null){
           if(cur.e.equals(e)){
               return true;
           }
           cur = cur.next;
       }
       return false;
   }

//链表中删除index(0-based)位置的元素，返回删除的元素
   public E remove(int index){
       if(index < 0 || index >= size)
           throw new IllegalArgumentException("Remove failed.Illeagl failed.");
       Node pre = dummyHead;
       for (int i = 0; i < index; i++) {
           pre = pre.next;
       }
       Node retNode = pre.next;
       pre.next = retNode.next;
       retNode.next = null;
       size--;

return retNode.e;
   }

//从链表中删除第一个元素
   public E removeFirst(){
       return remove(0);
   }

//从链表中删除最后一个元素
   public E removeLast(){
       return remove(size - 1);
   }
   @Override
   public String toString() {
       StringBuilder res = new StringBuilder();

//        Node cur = dummyHead.next;
//        while (cur != null){
//            res.append(cur + "->");
//            cur = cur.next;
//        }

for (Node cur = dummyHead.next; cur != null; cur = cur.next){
           res.append(cur + "->");
       }
       res.append("null");
       return res.toString();
   }
   public static void main(String[] args) {
       LinkedList<Integer> linkedList = new LinkedList<>();
       for (int i = 0; i < 5; i++) {
           linkedList.addFirst(i);
           System.out.println(linkedList);
       }

linkedList.add(2, 666);
       System.out.println(linkedList);

linkedList.remove(2);
       System.out.println(linkedList);

linkedList.removeFirst();
       System.out.println(linkedList);

linkedList.removeLast();
       System.out.println(linkedList);
   }
}

二、链表实现栈操作

使用第二章中的栈接口，创建第一节中的链表实现对象，实现栈的操作，具体如下：

public class LinkedListStack<E> implements Stack<E> {
   private LinkedList<E> list;
   public LinkedListStack(){
       list = new LinkedList<>();
   }

@Override
   public int getSize() {
       return list.getSize();
   }

@Override
   public boolean isEmpty() {
       return list.isEmpty();
   }

@Override
   public void push(E value) {
       list.addFirst(value);
   }

@Override
   public E pop() {
       return list.removeFirst();
   }

@Override
   public E peek() {
       return list.getFirst();
   }

@Override
   public String toString() {
       StringBuilder res = new StringBuilder();
       res.append("Stack : top");
       res.append(list);
       return res.toString();
   }

public static void main(String[] args) {
       LinkedListStack<Integer> stack = new LinkedListStack<>();
       for (int i = 0; i < 5; i++) {
           stack.push(i);
           System.out.println(stack);
       }

stack.pop();
       System.out.println(stack);
   }
}

三、链表实现队列操作

使用第二章中的队列接口，创建无头节点的链表实现队列操作，具体如下：

public class LinkedListQueue<E> implements Queue<E> {
   private class Node{
       public E e;
       public LinkedListQueue.Node next;

public Node(E e, LinkedListQueue.Node next){
           this.e = e;
           this.next = next;
       }

public Node(E e){
           this(e, null);
       }

public Node(){
           this(null,null);
       }

@Override
       public String toString() {
           return e.toString();
       }
   }

private Node head,tail;
   private int size;
   public LinkedListQueue(){
       head = null;
       tail = null;
       size = 0;
   }

@Override
   public int getSize() {
       return size;
   }

@Override
   public boolean isEmpty() {
       return size == 0;
   }

@Override
   public void enqueue(E e) {
       if(tail == null){
           tail = new Node(e);
           head = tail;
       }else{
           tail.next = new Node(e);
           tail = tail.next;
       }
       size++;
   }

@Override
   public E dequeue() {
       if (isEmpty())
           throw new IllegalArgumentException("Cannot dequeue form any empty queue.");
       Node retNode = head;
       head = head.next;
       retNode.next = null;
       if (head == null)
           tail = null;
       return retNode.e;
   }

@Override
   public E getFront() {
       if (isEmpty())
           throw new IllegalArgumentException("Cannot getFront form any empty queue.");
       return head.e;
   }

@Override
   public String toString() {
       StringBuilder res = new StringBuilder();
       res.append("Queue : front ");

Node cur = head;
       while (cur != null){
           res.append(cur + "->");
           cur = cur.next;
       }

res.append("Null tail");
       return res.toString();
   }

public static void main(String[] args) {
       LinkedListQueue<Integer> queue = new LinkedListQueue<>();
       for (int i = 0; i < 10; i++) {
           queue.enqueue(i);
           System.out.println(queue);

if(i ％ 3 == 2){
               queue.dequeue();
               System.out.println(queue);
           }
       }

}
}

来源：https://blog.csdn.net/weixin_42280618/article/details/117917438