Java数据结构之链表相关知识总结
程序员文章站
2022-03-27 18:37:51
一、链表1.1 概述链表是真正动态的数据结构，最简单的动态数据结构，基本用于辅助组成其他数据结构。数据存储在“节点”（node）中优点：真正的动态，不需要处理固定容量的问题缺点：丧失了随机访问的能力1...
一、链表
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数据结构之链表相关知识总结的文章就介绍到这了,更多相关java链表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！
推荐阅读
-
数据结构之链表中倒数第k个结点（C++/Java语言实现）
-
Java基础知识回顾之七 ----- 总结篇
-
JAVA WEB快速入门之从编写一个基于SpringBoot+Mybatis快速创建的REST API项目了解SpringBoot、SpringMVC REST API、Mybatis等相关知识
-
JAVA注解相关知识总结
-
Python基础总结之第八天开始【while循环以及for循环,循环嵌套等循环相关的知识点】（新手可相互督促）
-
java8新特性之stream流中reduce()求和知识总结
-
Java游戏服务器系列之Netty相关知识总结
-
Java非阻塞I/O模型之NIO相关知识总结
-
简单易懂的java8新特性之lambda表达式知识总结
-
菜鸟学JAVA之——数据结构，单链表实现、泛型（部分）