双链表--实现各操作

package fuxi.linkedlist;
/**
* @auther 张弢
* @create 2022-12-06 18:28
*/
public class LinkedList {
Node first=null;
Node last=null;
int size=0;//记录元素个数
public static void main(String[] args) {
LinkedList linkedList=new LinkedList();
linkedList.addTail("B");
linkedList.addTail("A");
linkedList.addTail("C");
linkedList.addTail("D");
linkedList.traverse();
System.out.println("节点数量："+linkedList.getSize());
System.out.println(linkedList.node(3).data);
linkedList.traverse();
System.out.print("n根据位置删除：");
linkedList.remove(3);
linkedList.traverse();
System.out.print("修改节点值：");
linkedList.update(2,"W");
linkedList.traverse();
System.out.print("n根据位置插入节点:");
linkedList.insert(3,"C");
linkedList.insert(3,"A");
linkedList.traverse();
System.out.print("n去重:");
linkedList.distinct();
linkedList.traverse();
System.out.print("n插入排序:");
linkedList.insertSort();
linkedList.traverse();
System.out.print("n链表转为数组：");
String[] strings = linkedList.toArray2();
for (String s:strings) System.out.print(s+" ");
}
//1.添加尾部
public void addTail(String val){
Node node=new Node();
node.data=val;
if (first==null){
first=last=node;
}else {
last.next=node;
node.prev=last;
last=node;
}
size++;
}
//2.添加头部
public void addFirst(String val){
Node node=new Node();
node.data=val;
if (first==null){
first=last=node;
}else {
first.prev=node;
node.next=first;
first=node;
}
size++;
}
//3.遍历
public void traverse(){
if (first==null)return;
Node temp=first;
while (temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
//4.获取节点数量
public int getSize(){
return size;
}
//5.判断链表是否为空
public boolean isEmpty(){
return size==0;
}
//6.位置检查
public void checkBoundary(int position){
if (position<0||position>size)
throw new RuntimeException("下标过啦");
}
//7.删除指定位置的节点
public Node remove(int position){
checkBoundary(position);//边界检查
Node node = node(position);//根据位置查找节点并返回
return unlink(node);//接触节点引用并返回
}
//8.根据指定位置返回节点
public Node node(int position){
Node temp=first;
for (int i=1;i<position;i++){
temp=temp.next;
}
return temp;
}
//9.解除节点的关系
public Node unlink(Node x){
//定义变量记录要解除引用的节点
Node temp=x;
//记录当前节点前驱
Node prev=x.prev;
//记录当前节点后继
Node next=x.next;
if (prev==null){
first=next;
}else {
prev.next=next;
x.prev=null;
}
if (next==null){
last=prev;
}else {
next.prev=prev;
x.next=null;
}
size--;
return temp;
}
//10.根据位置修改节点值
public void update(int position,String value){
checkBoundary(position);
node(position).data=value;//根据位置查找并返回节点，修改值
}
//11.获取指定节点的值
public String get(int position){
return node(position).data;
}
//12.指定位置插入节点
public void insert(int position,String val){
if (position==(size+1)){
addTail(val);
return;
}
if (position==1){
addFirst(val);
return;
}
Node node = create(val);//生成要插入的节点
Node res = node(position);//查找要插入位置的节点
res.prev.next=node;//创建新节点与与前节点的连接
node.prev=res.prev;
res.prev=node;//创建新节点与与后节点的连接
node.next=res;
size++;
}
//13.创建节点并返回
public Node create(String val){
Node node=new Node();
node.data=val;
return node;
}
//14.去重
public void distinct(){
Node current=first;
int pre=1;//记录被比较的是第几个数
while (current!=null){//每个节点向后比较一轮
Node nextCurrent=current.next;
int next=pre+1;
while (nextCurrent!=null){//nextCurrent与current比较后继续向后移动，直到null时此轮结束
if (current.data==nextCurrent.data){
nextCurrent=nextCurrent.next;
remove(next);
size--;
}else {
nextCurrent=nextCurrent.next;
next++;
}
}
//每轮比较完成后开始下一个数做为被比较的数
pre++;
current=current.next;
}
}
//15.判断链表是否包含某值
public boolean contains(String val){
Node temp=first;
while (temp!=null){
if (temp.equals(val)) return true;
temp=temp.next;
}
return false;
}
//15.插入排序
public void insertSort(){
Node current=first.next;//从第二个节点往前比较
while (current!=null){
Node prev=current.prev;
while (prev!=null){
//如果当前节点小于前一个节点就继续往前看
if (!(current.data.compareTo(prev.data)<0)) break;
prev=prev.prev;
}
//变量记录当前节点的位置
Node temp=current.next;
if (prev==null){//
String val = current.data;
unlink(current);
addFirst(val);
}else {
//把当前节点的前驱与后继关联上
//然后把当前节点插入到有序队伍指定位置，prev之后
current.prev.next=current.next;//prev后继改变
if (current.next!=null) current.next.prev=current.prev;//处理最后一个节点
current.next=prev.next;
prev.next.prev=current;//注意prev后继已经改变
prev.next=current;
current.prev=prev;
}
current=temp;
}
}
//16.链表转数组1
public String[] toArray1(){
String[] str=new String[size];
Node temp=first;
for (int i=0;i<size;i++){
str[i]=temp.data;
if (temp!=null) temp=temp.next;
}
return str;
}
//17.链表转数组2
public String[] toArray2(){
String[] str=new String[size];
for (int i=1;i<=size;i++){
str[i-1]=node(i).data;
}
return str;
}
}
class Node{
Node prev;//前驱
String data;//数据域
Node next;//后继
}

最后

以上就是顺心小蝴蝶为你收集整理的双链表--实现各操作的全部内容，希望文章能够帮你解决双链表--实现各操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。