数据结构~05.双链表的操作,手写Java语言中的LinkedList集合

爱被打了一巴掌 2023-02-28 08:45 82阅读 0赞

# 数据结构~05.双链表的操作,手写LinkedList集合 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

### 先写一个普通的双链表插入和遍历~ ###

### 删除结点的算法 ###

//在单链表的基础上做了稍稍修改~
    	q = p->next;
    	p->next = q->next;
    	q->next->pre = p;
    	free(q);

### 查找结点的算法 ###

Node* findNode(Node *C, int x) { 
    	Node* p = C->next;
    	while (p != NULL) { 
    		if (p ->data == x) { 
    			break;
    		}
    		p = p->next;
    	}
    	return p;
    }

### 奉上完整代码 ###

#include<stdio.h>
    #include<stdlib.h>
    typedef struct no_de { 
    	int data;				//data中存放数据域
    	struct no_de* pre;		//指向前驱结点的指针
    	struct no_de* next;		//指向后继结点的指针
    }Node;
    //建立头节点
    Node* getHead() { 
    	Node* head = (Node*)malloc(sizeof(Node));
    	head->data = NULL;
    	head->next = NULL;
    	head->pre = NULL;
    	return head;
    }
    //插入操作
    void Insert(Node *L,int data) { 
    	Node* p = (Node*)malloc(sizeof(Node));
    	p->data = data;
    	p->next = L->next;
    	p->pre = L;
    	L->next = p;
    }
    //删除操作
    int Delete(Node* C, int s) { 
    	Node* p, * q;
    	p = C;
    	//开始查找
    	while (p->next != NULL) { 
    		if (p->next->data == s) { 
    			break;
    		}
    		p = p->next;
    	}
    	if (p->next == NULL) { 
    		return 0;
    	}
    	else { 
    		//开始删除
    		q = p->next;
    		p->next = q->next;
    		q->next->pre = p;
    		free(q);
    		return 1;
    	}
    }
    //遍历链表
    void Print(Node *L) { 
    	Node* p = L->next;
    	//如果链表为空就输出[]
    	if (p == NULL) { 
    		printf("[]");
    	}
    	//遍历链表
    	while (p != NULL) { 
    		//判断是否到了最后
    		if (p ->next != NULL) { 
    			printf("%d->",p->data);
    		}
    		else { 
    			printf("%d",p->data);
    		}
    		p = p->next;
    	}
    	printf("\n");
    }
    //查找结点
    Node* findNode(Node *C, int x) { 
    	Node* p = C->next;
    	while (p != NULL) { 
    		if (p ->data == x) { 
    			break;
    		}
    		p = p->next;
    	}
    	return p;
    }
    int main(int argc,char * argv[]) { 
    	Node* list = getHead();
    	Insert(list,1); Insert(list, 2); Insert(list, 3); Insert(list, 4);
    	Delete(list,2);
    	Print(list);
    	Node* p = findNode(list,3);
    	printf("%d",p->data);
    	getchar();
    	return 0;
    }

## 采用尾插法建立双链表? ##

void InsertLast(Node*& L, int a[], int n) { 
    	Node* s, * r;
    	int i;
    	L = (Node*)malloc(sizeof(Node));
    	L->pre = NULL;
    	L->next = NULL;
    	//这里和单链表一样, r始终指向终端结点
    	r = L;
    	for (i = 0; i < n; ++i) { 
    		//建立新结点
    		s = (Node*)malloc(sizeof(Node));
    		s->data = a[i];
    		//将s 插入到 L的尾部，并且r 指向 s
    		r->next = s;
    		s->pre = r;
    		r = s;
    	}
    	r->next = NULL;
    }

## Java中的LinkedList ##

### 定义List接口 ###

public interface List <E>{ 
        int size();
        boolean isEmpty();
        boolean contains(E element);
        void add(E element);
        E get(int index);
        E set(int index,E element);
        void add(int index,E element);
        E remove(int index);
        int indexOf(E element);
        void clear();
        String toString();
    }

### 接口实现 ###

public class LinkedList<E> implements List<E>{ 
    
        private int size;   //集合的长度
        private Node first;
        private Node last;
    
        @Override
        public int size() { 
            return size;
        }
    
        //判断当前集合中是否有元素
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //判断当前元素是否存在
        @Override
        public boolean contains(E element) { 
            return indexOf(element) > -1;
        }
    
        @Override
        public void add(E element) { 
            //调用下面的add方法,根据size保证每次都添加在最后
            add(size,element);
        }
        //取得坐标位置上的节点
        private Node<E> node(int index){ 
            Node N = first; //指向头
            //先判断要查找的index,是靠近头还是靠近尾
            //如果靠近头就从头开始查找,如果靠近尾就从尾开始查找
            //方法: 根据index 和 size的一半去比较
            if(index > (size >> 1)){ 
                //靠近尾
                N = last;   //指向尾
                for(int i = size-1; i > index; i--){ 
                    N = N.pre;
                }
            }else{ 
                //靠近头
                for(int i = 0; i < index; i++){ 
                    N = N.next;
                }
            }
            return N;
        }
    
        @Override
        public E get(int index) { 
            //防止坐标越界
            if(index < 0 || index >= size){ 
                throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
            }
            //调用方法
            return node(index).element;
        }
    
        @Override
        public E set(int index, E element) { 
            //获得index上的node
            Node<E> node = node(index);
            //保存原来的值
            E oldElement = node.element;
            //新值覆盖老值
            node.element = element;
            //返回老值
            return oldElement;
        }
    
        @Override
        public void add(int index, E element) { 
            //当需要添加到末尾时
            if(index == size) { 
                //拿到last节点
                Node l = last;
                //构建node 完成指向关系
                Node newNode = new Node(l,null,element);
                //将原来的last 节点的next 修改成新构建出来的node
                last = newNode;
                if(l == null){ 
                    first = newNode;
                }else { 
                    l.next = newNode;
                }
            }else{ 
                //获得指定的index
                Node<E> node = node(index);
                //获得前一个结点
                Node<E> pre = node.pre;
                //构建新的now 完成指向关系
                Node<E> newNode = new Node(pre, node, element);
                //改变指向
                pre.next = newNode;
                if (pre == null) { 
                    first = newNode;
                } else { 
                    node.pre = newNode;
                }
            }
            size++;
        }
    
        //链表删除的主要原理就是将被删除者的前一个元素指向后一个元素
        //比如 A->B->C 当我要删除B的时候,就让A -> C
        @Override
        public E remove(int index) { 
            //防止坐标越界
            if(index < 0 || index >= size){ 
                throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
            }
            //获得要删除的元素Node
            Node<E>node = node(index);
            //获得前一个结点
            Node<E> pre = node.pre;
            //获得后一个结点
            Node<E> next = node.next;
    
            if(pre == null){ 
                //firest进行修改
                first = next;
                next.pre = null;
            }else{ 
                //改变前一个结点的next
                pre.next = next;
            }
            
            if(next == null){ 
                //last进行修改
                last = pre;
            }else{ 
                next.pre = pre;
            }
            size--;
            //返回老元素
            return node.element;
        }
    
        @Override
        public int indexOf(E element) { 
            //查找element元素是否存在,有返回索引,没有返回-1
            Node N = first;
            int index = 0;
            //遍历
            for(Node i = N; i != null; i = i.next){ 
                if(element == i.element){ 
                    return index;
                }
                index++;
            }
            return -1;
        }
    
        @Override
        public void clear() { 
            size = 0;
            first = null;
            last = null;
        }
    
        public String toString(){ 
            Node N = first;
            StringBuilder stringBuilder = new StringBuilder("[");
            boolean flag = false;   //判断是否循环到了最后
            for(Node i = N; i != null; i = i.next){ 
                //说明已经到了最后一个元素
                if(i.next == null) { 
                    flag = true;
                }
                //如果没到最后就加 逗号
                if(flag == false){ 
                    stringBuilder.append(i.element + ",");
                }else{   //到了最后就不加逗号
                    stringBuilder.append(i.element);
                }
            }
            stringBuilder.append("]");
            return stringBuilder.toString();
        }
    
        //内部Node节点类
        private static class Node<E>{ 
            Node<E> pre;
            Node<E> next;
            E element;
            public Node(Node next,E element){ 
                this.next = next;
                this.element = element;
            }
    
            public Node(Node pre,Node next,E element){ 
                this.pre = pre;
                this.next = next;
                this.element = element;
            }
    
            public Node() { 
    
            }
        }
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107399270