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

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

一、链表

1.1 概述

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

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

优点：真正的动态，不需要处理固定容量的问题

缺点：丧失了随机访问的能力

1.2 链表使用的基本功能

定义Node节点

private class Node{

public E e;

public Node nexthttp://;

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++;

}

向链mpitFWr表中删除元素

具体代码实现：

//链表中删除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 {

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 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 implements Stack {

private LinkedList 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 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 implements Queue {

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 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);

}

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。