Java数据结构之链表的相关知识有哪些

这篇文章主要介绍了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);             }         }     } }

感谢你能够认真阅读完这篇文章，希望小编分享的“Java数据结构之链表的相关知识有哪些”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!