什么是链表?
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
每一个链表都包含多个节点,节点又包含两个部分,一个是数据域(储存节点含有的信息),一个是引用域(储存下一个节点或者上一个节点的地址)。
链表的理解示意图:
链表的特点是什么?
获取数据麻烦,需要遍历查找,比数组慢
方便插入、删除
简单的链表的实现原理
创建一个节点类,其中节点类包含两个部分,第一个是数据域(你到时候要往节点里面储存的信息),第二个是引用域(相当于指针,单向链表有一个指针,指向下一个节点;双向链表有两个指针,分别指向下一个和上一个节点)
创建一个链表类,其中链表类包含三个属性:头结点、尾节点和大小,方法包含添加、删除、插入等等方法。 通用节点抽象类
package com.lineardatastructure.linked;
public abstract class LinkedAbs<T> implements Iterable<T> {
//列表长度
public int size = 0;
//当前节点
public Node head;
//尾节点
public Node end;
//节点
protected class Node {
Node previous = null;//上一个结点
Node next = null;//下一个结点
T data;//结点数据
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
public Node(Node next, Node previous) {
this.next = next;
this.previous = previous;
}
public Node(T data, Node next, Node previous) {
this.next = next;
this.previous = previous;
}
public Node(T data) {
this.data = data;
}
}
public Node isRinged(){
if(head == null){
return null;
}
Node slow = head;
Node fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return fast;
}
}
return null;
}
// 获取链表头元素
public T getFrom() {
return head.data;
}
//获取链表结尾元素
public T getEnd() {
return end.data;
}
//获取链表中元素个数
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void stackDestroy() {
head = null;
size = 0;
end=null;
}
//寻找单链表的中间结点:
public abstract T findMiddle();
public abstract void reserveLink();
public abstract T get(int index);
public abstract void addFirst(T e);
public abstract void addlast(T e);
public abstract void add(T e);
public abstract boolean remove(T obj);
public abstract boolean remove(int index);
public abstract boolean removeFirst();
public abstract boolean removeLast();
}
实现单向链表
package com.lineardatastructure.linked;
import java.util.Iterator;
// 单向链表
public class OneWayLinked<T> extends LinkedAbs<T> {
@Override
public void reserveLink() {
Node curNode = head;//头结点
Node preNode = null;//前一个结点
while(curNode != null){
Node nextNode = curNode.next;//保留下一个结点
curNode.next = preNode;//指针反转
preNode = curNode;//前结点后移
curNode = nextNode;//当前结点后移
}
head = preNode;
}
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是链表结点个数为奇数时,快指针已经走到最后了
//quickPoint.next.next == null是链表结点数为偶数时,快指针已经走到倒数第二个结点了
//链表结点个数为奇数时,返回的是中间结点;链表结点个数为偶数时,返回的是中间两个结点中的前一个
while (quickPoint.next != null && quickPoint.next.next != null) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
@Override
public T get(int index) {
if(size<0 || index>size){//待查询结点不存在
return null;
}
if(index == 0){//查询头结点
return head.data;
}
Node curNode =head;
int i = 0;
while (curNode != null) {
if(i==index){//寻找到待查询结点
return curNode.data;
}
//当先结点和前结点同时向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
}
@Override
public void addlast(T e) {
}
@Override
public void add(T data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
end=head;//添加尾节点
size++;
return;
}
Node temp = end;
temp.next = newNode;
end=newNode;//修改尾节点
size++;
}
@Override
public boolean remove(T obj) {
if (head.data.equals(obj)) {//删除头结点
head = head.next;
size=0;
return true;
}
Node preNode = head;
Node curNode = preNode.next;
while (curNode != null) {
if (curNode.data.equals(obj)) {//寻找到待删除结点
preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
size--;
return true;
}
//当先结点和前结点同时向后移
preNode = preNode.next;
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if(size<0 || index>size){//待删除结点不存在
return false;
}
if(index == 0){//删除头结点
head = head.next;
return true;
}
Node preNode = head;
Node curNode =head.next;
int i =1; //从第2个值开始
while(preNode.next != null){
if(i==index){//寻找到待删除结点
preNode.next= curNode.next;//待删除结点的前结点指向待删除结点的后结点
return true;
}
//当先结点和前结点同时向后移
preNode=curNode;
curNode = curNode.next;
i++;
}
return false;
}
@Override
public boolean removeFirst() {
return false;
}
@Override
public boolean removeLast() {
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null) {
data = cursor.data;
cursor = cursor.next;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
OneWayLinked.this.remove(data);
}
};
}
}
单向环形链表
它和单链表的区别在于结尾点的指针域不是指向null,而是指向头结点,形成首尾相连的环。这种首尾相连的单链表称为单向循环链表。循环链表可以从任意一个结点出发,访问到链表中的全部结点。
单向循环链表的查找、删除和修改操作与单链表一致(这里不在赘述,可参考前面的内容),插入操作和单链表有所不同,单向循环链表需要维持环状结构。判断单链表为空的条件是head.next == null,而判断单向循环链表为空的条件为head.next == head。
package com.lineardatastructure.linked;
import java.util.Iterator;
// 单向循环链表
public class OneLoopWayLinked<T> extends LinkedAbs<T> {
@Override
public void reserveLink() {
Object[] ts = new Object[size];
int i = size - 1;
for (T t : this) {
ts[i] = t;
i--;
}
Node node = head;
node.data = (T) ts[0];
for (int i1 = 1; i1 < ts.length; i1++) {
Node node1 = new Node((T) ts[i1]);
node.next = node1;
node = node1;
end= node1;
}
//调整位置
end.next=head;
}
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是链表结点个数为奇数时,快指针已经走到最后了
//quickPoint.next.next == null是链表结点数为偶数时,快指针已经走到倒数第二个结点了
//链表结点个数为奇数时,返回的是中间结点;链表结点个数为偶数时,返回的是中间两个结点中的前一个
while (quickPoint.next != head && quickPoint.next.next != head) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
@Override
public T get(int index) {
if (size < 0 || index > size) {//待查询结点不存在
return null;
}
if (index == 0) {//查询头结点
return head.data;
}
Node curNode = head.next;
int i = 1;
while (curNode != head) {
if (i == index) {//寻找到待查询结点
return curNode.data;
}
//当先结点和前结点同时向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
}
@Override
public void addlast(T e) {
}
@Override
public void add(T data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head; //环型
end = head;//添加尾节点
size++;
return;
}
Node temp = end;
//一直遍历到最后
temp.next = newNode;
newNode.next = head;//环型
end = newNode;//修改尾节点
size++;
}
@Override
public boolean remove(T obj) {
if (head.data.equals(obj)) {//删除头结点
head = head.next;
end.next=head;//调整环
size--;
return true;
}
Node preNode = head;
Node curNode = preNode.next;
while (curNode != head) {
if (curNode.data.equals(obj)) {//寻找到待删除结点
preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
size--;
return true;
}
//当先结点和前结点同时向后移
preNode = preNode.next;
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if (size < 0 || index > size) {//待删除结点不存在
return false;
}
if (index == 0) {//删除头结点
head = head.next;
end.next=head;//调整环
size--;
return true;
}
Node preNode = head;
Node curNode = head.next;
int i = 1; //从第2个值开始
while (preNode.next != head) {
if (i == index) {//寻找到待删除结点
preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
return true;
}
//当先结点和前结点同时向后移
preNode = curNode;
curNode = curNode.next;
i++;
}
size--;
return false;
}
@Override
public boolean removeFirst() {
return false;
}
@Override
public boolean removeLast() {
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null&&cursor.next != head) {
data = cursor.data;
cursor = cursor.next;
return true;
}
if (cursor != null) {
data = cursor.data;
cursor = null;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
OneLoopWayLinked.this.remove(data);
}
};
}
}
实现双向链表
package com.lineardatastructure.linked;
import java.util.Iterator;
public class BothwayLinked<T> extends LinkedAbs<T> {
@Override
public T get(int index) {
if (size < 0 || index > size) {//待查询结点不存在
return null;
}
if (index == 0) {//查询头结点
return head.data;
}
Node curNode = head;
int i = 0;
while (curNode != null) {
if (i == index) {//寻找到待查询结点
return curNode.data;
}
//当先结点和前结点同时向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
Node next = head;
Node previous = new Node(e);
previous.next = next;
next.previous = previous;
head=previous;
size++;
}
@Override
public void addlast(T e) {
Node newNode = new Node(e);
if (head == null) {
head = newNode;
size++;
end=head;//添加尾节点
return;
}
Node temp = end;
temp.next = newNode;
newNode.previous = temp;
end=newNode;//修改尾节点
size++;
}
@Override
public void add(T e) {
addlast(e);
}
@Override
public boolean remove(T obj) {
if (removeHead()) {
return true;
}
Node curNode = head;
while (curNode != null) {
//寻找到待删除结点
if (curNode.data.equals(obj)) {
//将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//删除的是最后节点,那么就把他上一个节点的下一个节点删除
previous.next=null;
} else if (previous==null) {
//删除的是头节点的话,那么就不管父节点了
head=head.next;
head.previous=null;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//当先结点向后移
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if (index<0 ||index >= size) {//待删除结点不存在
return false;
}
if (removeHead()) {
return true;
}
Node curNode = head;
int i = 0;
while (curNode != null) {
if (i == index) {//寻找到待删除结点
//将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//删除的是最后节点,那么就把他上一个节点的下一个节点删除
previous.next=null;
} else if (previous==null) {
//删除的是头节点的话,那么就不管父节点了
head=head.next;
head.previous=null;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//当先结点向后移
curNode = curNode.next;
i++;
}
return false;
}
@Override
public boolean removeFirst() {
if (removeHead()) {
return true;
}
Node node = head.next;
node.previous = null;
head = node;
size--;
return false;
}
@Override
public boolean removeLast() {
if (removeHead()) {
return true;
}
//删除尾节点
end.previous.next=null;
size--;
return true;
}
//如果只有一个元素那么就将头删除
public boolean removeHead() {
if (head.next==null) {
head=null;
return true ;
}
return false;
}
@Override
public void reserveLink() {
Object[] ts = new Object[size];
int i = size - 1;
for (T t : this) {
ts[i] = t;
i--;
}
Node node = head;
node.data = (T) ts[0];
for (int i1 = 1; i1 < ts.length; i1++) {
Node node1 = new Node((T) ts[i1]);
node.next = node1;
node1.previous = node;
node = node1;
}
}
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是链表结点个数为奇数时,快指针已经走到最后了
//quickPoint.next.next == null是链表结点数为偶数时,快指针已经走到倒数第二个结点了
//链表结点个数为奇数时,返回的是中间结点;链表结点个数为偶数时,返回的是中间两个结点中的前一个
while (quickPoint.next != null && quickPoint.next.next != null) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null) {
data = cursor.data;
cursor = cursor.next;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
BothwayLinked.this.remove(data);
}
};
}
}
双向循环链表
相比单链表,双向循环链表是一个更加复杂的结构。因为双向循环链表的节点不仅包含指向下一个节点的指针(next),还包含指向前一个节点的指针(prev)。
在双向循环链表中,可见的不只有头指针head,还有尾节点end。这是和单链表的区别。
双向循环链表的头指针head的前一个节点指向end,尾节点end的后一个节点指向head。
注意: 双向循环链表,实现反查询特别容易只需要反过来遍历一遍就行
package com.lineardatastructure.linked;
import org.w3c.dom.Node;
import java.util.Iterator;
public class BothwayLoopLinked<T> extends LinkedAbs<T> {
@Override
public void reserveLink() {
Object[] ts = new Object[size];
int i = size - 1;
for (T t : this) {
ts[i] = t;
i--;
}
Node node = head;
node.data = (T) ts[0];
for (int i1 = 1; i1 < ts.length; i1++) {
Node node1 = new Node((T) ts[i1]);
node.next = node1;
node1.previous = node;
node = node1;
end= node1;
}
//调整位置
head.previous=end;
end.next=head;
}
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是链表结点个数为奇数时,快指针已经走到最后了
//quickPoint.next.next == null是链表结点数为偶数时,快指针已经走到倒数第二个结点了
//链表结点个数为奇数时,返回的是中间结点;链表结点个数为偶数时,返回的是中间两个结点中的前一个
while (quickPoint.next != head && quickPoint.next.next != head) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
@Override
public T get(int index) {
if (size < 0 || index > size) {//待查询结点不存在
return null;
}
if (index == 0) {//查询头结点
return head.data;
}
Node curNode = head.next;
int i = 1;
while ( curNode!= head) {
if (i == index) {//寻找到待查询结点
return curNode.data;
}
//当先结点和前结点同时向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
Node next = head;
Node previous = new Node(e);
previous.previous = head.previous;
previous.next = next;
next.previous = previous;
head = previous;
end.next=previous;//修改尾节点的指向
size++;
}
@Override
public void addlast(T e) {
Node newNode = new Node(e);
if (head == null) {
head = newNode;
head.previous=head;//环型
head.next=head; //环型
end=head;//添加尾节点
size++;
return;
}
Node temp = end;
temp.next = newNode;
newNode.previous = temp;
newNode.next = head;//给为节点添加头节点(环型)
end=newNode;//修改尾节点
size++;
}
@Override
public void add(T e) {
addlast(e);
}
@Override
public boolean remove(T obj) {
if (removeHead()) {
return true;
}
//头部删除需要特殊处理
if (obj == head.data) {
Node previous = head.previous;
head = head.next;
head.previous = previous;
end.next=head;
size--;
return true;
}
Node curNode = head.next;
while (curNode != head) {
//寻找到待删除结点
if (curNode.data.equals(obj)) {
//将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//删除的是最后节点,那么就把他上一个节点的下一个节点删除
previous.next = null;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//当先结点向后移
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if (removeHead()) {
return true;
}
if (size < 0 || index >= size) {//待删除结点不存在
return false;
}
//头部删除需要特殊处理
if (index==0) {
Node previous = head.previous;
head = head.next;
head.previous = previous;
size--;
return true;
}
Node curNode = head.next;
int i = 1;
while (curNode != null) {
if (i == index) {//寻找到待删除结点
//将删除的节点后节点,覆盖删除的节点,然后将父节点指向被删除元素的父节点
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//删除的是最后节点,那么就把他上一个节点的下一个节点给替换成头节点
previous.next = head;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//当先结点向后移
curNode = curNode.next;
i++;
}
return false;
}
@Override
public boolean removeFirst() {
head = head.next;
head.previous = end; //环绕
end.next=head; //环绕
size--;
return false;
}
@Override
public boolean removeLast() {
//将删除结尾节点
end.previous.next=head;
size--;
return true;
}
//如果只有一个元素那么就将头删除
public boolean removeHead() {
if (head.next==null) {
head=null;
return true ;
}
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null&&cursor.next != head) {
data = cursor.data;
cursor = cursor.next;
return true;
}
if (cursor != null) {
data = cursor.data;
cursor = null;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
BothwayLoopLinked.this.remove(data);
}
};
}
}
到此这篇关于Java实现链表数据结构的文章就介绍到这了,更多相关Java链表数据结构内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!