diff --git a/services/core/java/com/android/server/notification/NotificationManagerService.java b/services/core/java/com/android/server/notification/NotificationManagerService.java
index 19c9d9b..778ace2 100644
--- a/services/core/java/com/android/server/notification/NotificationManagerService.java
+++ b/services/core/java/com/android/server/notification/NotificationManagerService.java
@@ -3863,14 +3863,18 @@
     private void cancelNotificationLocked(NotificationRecord r, boolean sendDelete, int reason) {
         final String canceledKey = r.getKey();
 
-        // Remove from either list
-        boolean wasPosted;
-        if (mNotificationList.remove(r)) {
-            mNotificationsByKey.remove(r.sbn.getKey());
+        // Remove from both lists, either list could have a separate Record for what is effectively
+        // the same notification.
+        boolean wasPosted = false;
+        NotificationRecord recordInList = null;
+        if ((recordInList = findNotificationByListLocked(mNotificationList, r.getKey())) != null) {
+            mNotificationList.remove(recordInList);
+            mNotificationsByKey.remove(recordInList.sbn.getKey());
             wasPosted = true;
-        } else {
-            mEnqueuedNotifications.remove(r);
-            wasPosted = false;
+        }
+        if ((recordInList = findNotificationByListLocked(mEnqueuedNotifications, r.getKey()))
+                != null) {
+            mEnqueuedNotifications.remove(recordInList);
         }
 
         // Record caller.
@@ -4294,17 +4298,12 @@
     // TODO: need to combine a bunch of these getters with slightly different behavior.
     // TODO: Should enqueuing just add to mNotificationsByKey instead?
     private NotificationRecord findNotificationByKeyLocked(String key) {
-        final int N = mNotificationList.size();
-        for (int i = 0; i < N; i++) {
-            if (key.equals(mNotificationList.get(i).getKey())) {
-                return mNotificationList.get(i);
-            }
+        NotificationRecord r;
+        if ((r = findNotificationByListLocked(mNotificationList, key)) != null) {
+            return r;
         }
-        final int M = mEnqueuedNotifications.size();
-        for (int i = 0; i < M; i++) {
-            if (key.equals(mEnqueuedNotifications.get(i).getKey())) {
-                return mEnqueuedNotifications.get(i);
-            }
+        if ((r = findNotificationByListLocked(mEnqueuedNotifications, key)) != null) {
+            return r;
         }
         return null;
     }
@@ -4322,8 +4321,7 @@
     }
 
     private NotificationRecord findNotificationByListLocked(ArrayList<NotificationRecord> list,
-            String pkg, String tag, int id, int userId)
-    {
+            String pkg, String tag, int id, int userId) {
         final int len = list.size();
         for (int i = 0; i < len; i++) {
             NotificationRecord r = list.get(i);
@@ -4335,6 +4333,18 @@
         return null;
     }
 
+    private NotificationRecord findNotificationByListLocked(ArrayList<NotificationRecord> list,
+            String key)
+    {
+        final int N = list.size();
+        for (int i = 0; i < N; i++) {
+            if (key.equals(list.get(i).getKey())) {
+                return list.get(i);
+            }
+        }
+        return null;
+    }
+
     // lock on mNotificationList
     int indexOfNotificationLocked(String key) {
         final int N = mNotificationList.size();
diff --git a/services/tests/notification/src/com/android/server/notification/NotificationManagerServiceTest.java b/services/tests/notification/src/com/android/server/notification/NotificationManagerServiceTest.java
index db010b8..88f1a53 100644
--- a/services/tests/notification/src/com/android/server/notification/NotificationManagerServiceTest.java
+++ b/services/tests/notification/src/com/android/server/notification/NotificationManagerServiceTest.java
@@ -280,6 +280,21 @@
 
     @Test
     @UiThreadTest
+    public void testCancelNotificationWhilePostedAndEnqueued() throws Exception {
+        mBinderService.enqueueNotificationWithTag(mContext.getPackageName(), "opPkg", "tag", 0,
+                generateNotificationRecord(null).getNotification(), new int[1], 0);
+        waitForIdle();
+        mBinderService.enqueueNotificationWithTag(mContext.getPackageName(), "opPkg", "tag", 0,
+                generateNotificationRecord(null).getNotification(), new int[1], 0);
+        mBinderService.cancelNotificationWithTag(mContext.getPackageName(), "tag", 0, 0);
+        waitForIdle();
+        StatusBarNotification[] notifs =
+                mBinderService.getActiveNotifications(mContext.getPackageName());
+        assertEquals(0, notifs.length);
+    }
+
+    @Test
+    @UiThreadTest
     public void testCancelNotificationsFromListenerImmediatelyAfterEnqueue() throws Exception {
         final StatusBarNotification sbn = generateNotificationRecord(null).sbn;
         mBinderService.enqueueNotificationWithTag(sbn.getPackageName(), "opPkg", "tag",