赞
踩
文章目录
构造方法:
方法 | 解释 |
LinkedList()
|
无参构造
|
public LinkedList(Collection<? extends E> c)
|
使用其他集合容器中元素构造List
|
- public static void main(String[] args) {
- // 构造一个空的LinkedList
- List<Integer> list1 = new LinkedList<>();
-
- List<String> list2 = new java.util.ArrayList<>();
- list2.add("JavaSE");
- list2.add("JavaWeb");
- list2.add("JavaEE");
- // 使用ArrayList构造LinkedList
- List<String> list3 = new LinkedList<>(list2);
- }
LinkedList的常用方法:
方法 | 解释 |
boolean add(E e)
|
尾插 e
|
void add(int index, E element)
|
将 e 插入到 index 位置
|
boolean addAll(Collection<? extends E> c)
|
尾插 c 中的元素
|
E remove(int index)
|
删除 index 位置元素
|
boolean remove(Object o)
|
删除遇到的第一个 o
|
E get(int index)
|
获取下标 index 位置元素
|
E set(int index, E element)
|
将下标 index 位置元素设置为 element
|
void clear()
|
清空
|
boolean contains(Object o)
|
判断 o 是否在线性表中
|
int indexOf(Object o)
|
返回第一个 o 所在下标
|
int lastIndexOf(Object o)
|
返回最后一个 o 的下标
|
List<E> subList(int fromIndex, int toIndex)
|
截取部分 list
|
LinkedList的遍历:(foreach遍历、使用迭代器遍历---正向遍历、使用反向迭代器---反向遍历
- LinkedList<String> list = new LinkedList<>();
- list.add("javaSE");
- list.add("javaWeb");
- list.add("javaEE");
- // foreach遍历
- for (String x: list) {
- System.out.print(x + " ");
- }
- // 使用迭代器遍历---正向遍历
- ListIterator<String> list1 = list.listIterator();
- while (list1.hasNext()){
- System.out.print(list1.next()+" ");
- }
- // 使用反向迭代器---反向遍历
- ListIterator<String> lis2 = list.listIterator(list.size());
- while (lis2.hasPrevious()){
- System.out.print(lis2.previous()+" ");
- }
- public class MyLinkedList {
- static class ListNode{
- int val;
- ListNode pre;
- ListNode next;
- public ListNode(int val){
- this.val = val;
- }
- }
- public ListNode head;//头部
- public ListNode tail;//尾部
-
- public void addFirst(int data){
- ListNode node = new ListNode(data);
- if (head == null){
- head = node;
- tail = node;
- return;
- }
- node.next = head;
- head.pre = node;
- head = node;
- }
- public void addLast(int data){
- ListNode node = new ListNode(data);
- if (head == null){
- head = node;
- tail = node;
- return;
- }
- tail.next = node;
- node.pre = tail;
- tail = node;
- }
- //任意位置插入,第一个数据节点为0号下标
- public boolean addIndex(int index,int data){
- if (index < 0 || index > size()){
- System.out.println("index位置不合法!");
- return false;
- }
- if (index == 0){
- addFirst(data);
- return true;
- }
- if (index == size()){
- addLast(data);
- return true;
- }
- ListNode indexNode = findNode(index);
- ListNode node = new ListNode(data);
- node.pre = indexNode.pre;
- indexNode.pre.next = node;
- node.next = indexNode;
- indexNode.pre = node;
- return true;
- }
- public ListNode findNode(int index){
- ListNode cur = head;
- while (index != 0){
- cur = cur.next;
- index--;
- }
- return cur;
- }
- public boolean contains(int key){
- ListNode cur = head;
- while (cur != null){
- if (cur.val == key)return true;
- cur = cur.next;
- }
- return false;
- }
- public void remove(int key) {
- ListNode cur = head;
- while (cur != null) {
- if (cur.val == key) {
- if (cur == head) {
- head = head.next;
- if (head != null) {
- head.pre = null;
- } else {
- tail = null;
- }
- } else {
- cur.pre.next = cur.next;
- if (cur.next != null) {
- cur.next.pre = cur.pre;
- } else {
- tail = tail.pre;
- }
- }
- return;
- }
- cur = cur.next;
- }
- }
-
- public void removeAllKey(int key) {
- ListNode cur = head;
- while (cur != null) {
- if (cur.val == key) {
- if (cur == head) {
- head = head.next;
- if (head != null) {
- head.pre = null;
- } else {
- tail = null;
- }
- } else {
- cur.pre.next = cur.next;
- if (cur.next != null) {
- cur.next.pre = cur.pre;
- } else {
- tail = tail.pre;
- }
- }
- }
- cur = cur.next;
- }
- }
- public int size(){
- ListNode cur = head;
- int count = 0;
- while (cur != null){
- count++;
- cur = cur.next;
- }
- return count;
- }
- public void display(){
- ListNode cur = head;
- while (cur != null){
- System.out.print(cur.val + " ");
- cur = cur.next;
- }
- }
- public void clear(){
- ListNode cur = head;
- while (cur != null){
- ListNode temp = cur.next;
- cur.next = null;
- cur.pre = null;
- cur = temp;
- }
- head = null;
- tail = null;
- }
- }
递归逆序打印:
- public void display(ListNode head) {
- if(head == null) {
- return;
- }
- if(head.next == null) {
- System.out.print(head.val+" ");
- return;
- }
- display(head.next);
- System.out.print(head.val+" ");
- }
非递归逆序打印(用栈实现):
- public void display(ListNode head) {
- if (head == null) {
- return;
- }
- Stack<ListNode> stack = new Stack<>();
- ListNode cur = head;
- while (cur != null) {
- stack.push(cur);
- cur = cur.next;
- }
- while (!stack.empty()) {
- ListNode ret = stack.pop();
- System.out.print(ret.val+" ");
- }
- }
ArrayList实质是顺序表,底层是一个数组。LinkedList实质是一个链表。
他们都具有增删查改的功能,但是在实现方式上有区别。比如在插入元素的时候,ArrayList往0位置上插入一个元素,就需把整个数组整体往后移动,时间复杂度为O(N)。而LinkedList只需要修改指向就可以了,时间复杂度为O(1)。但是ArrayList可以支持随机访问,时间复杂度为O(1),所以一般情况下ArrayList顺序表适合频繁根据下标位置访问,LinkedList比较适合插入和删除比较频繁的情况。
从存储上来说,ArrayList顺序表在物理上和逻辑上都是连续的,但是在扩容的时候,可能会造成空间的浪费。而LinkedList在物理上不一定是连续的,在逻辑上是连续的,可以做到随用随取。
不同点 | ArrayList | LinkedList |
存储空间上
|
物理上逻辑上一定连续
|
逻辑上连续,但物理上不一定连续
|
随机访问
|
支持O(1)
|
不支持:O(N)
|
头插
|
需要搬移元素,效率低O(N)
|
只需修改引用的指向,时间复杂度为O(1)
|
插入
|
空间不够时需要扩容
|
没有容量的概念
|
应用场景
|
元素高效存储+频繁访问
|
任意位置插入和删除频繁
|
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。